Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 2014

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: maszyny alternatywne

Sortuj według:

Ogranicz wyniki do:

Algorytmy genetyczne w zagadnieniu harmonogramowania zadań w systemach złożonych z maszynami alternatywnymi. Sposoby reprezentacji.

Warżołek D., Gola Ł.

Gospodarka Materiałowa i Logistyka

2014

nr 11

135--140

Problem harmonogramowania zadań w systemach złożonych z maszynami alternatywnymi (ang. flexible job-shop scheduling problem, F-JSSP) stanowi naturalne rozszerzenie (uogólnienie) problemu harmonogramowania zadań w klasycznych systemach typu job-shop (ang. classical job-shop, general job-shop), poprzez modyfikację jednego z jego głównych założeń. Modyfikacja ta polega na dopuszczeniu możliwości przypisywania operacjom (zadaniom) produkcyjnym więcej niż jednej maszyny, na których mogą być one zrealizowane. Wprowadzenie tej zmiany spowodowało, że problem harmonogramowania zadań w systemach złożonych z maszynami alternatywnymi podzielony został na dwa mniejsze podproblemy tj. na: problem przydziału maszyn do wykonania określonych zadań (ang. machine assignement sub-problem) i problem ich harmonogramowania (ang. scheduling sub-problem). Z uwagi na to, że klasyczny problem typu job-shop jest problemem NP-trudnym (ang. NP-hard problem) to do tej samej klasy problemów zaliczany jest także problem harmonogramowania zadań w systemach złożonych z maszynami alternatywnymi stanowiący o wiele bardziej złożoną jego wersję. Warto dodać, że do klasy problemów NP-trudnych zalicza się najtrudniejsze do rozwiązania problemy optymalizacji kombinatorycznej (ang. combinatorial optimization problems, COPs) tzn. takie, które nie są rozwiązywane w czasie wielomianowym. Ta cecha powoduje, że czasowa złożoność obliczeniowa (ang. time computational complexity), lub w skrócie, złożoność czasowa (ang. time complexity) algorytmów opracowywanych do rozwiązywania tej klasy problemów wzrasta w sposób ekspotencjalny wraz z rozmiarem problemu . W ciągu ostatnich 30-40 lat, w literaturze zaproponowanych zostało wiele metod (algorytmów) do rozwiązywania problemów optymalizacji kombinatorycznej. Generalnie, metody te podzielić można według różnych kryteriów, spośród których za najważniejsze uznaje się podział biorący pod uwagę uzyskiwaną dokładność rozwiązywanego problemu. W zależności od uzyskanej dokładności rozwiązania wyróżnia się: algorytmy dokładane (ang. exact algorithms), algorytmy przybliżone (ang. approximate algorithms) i algorytmy heurystyczne (ang. heuristic algorithms). Algorytmy przybliżone oraz algorytmy heurystyczne, w literaturze, często określane są także wspólnym mianem algorytmów niedokładnych (ang. inexact algorithms) lub przybliżonych. Do algorytmów przybliżonych (niedokładanych), które służą do rozwiązywania trudnych problemów optymalizacji kombinatorycznej takich właśnie jak omawiany problem zalicza się m.in. grupę metod nazywaną algorytmami ewolucyjnymi (ang. evolutionary algorithms), do których zalicza się m.in. algorytmy genetyczne. Głównym celem tego artykułu jest przedstawienie sposobów wykorzystania algorytmów genetycznych w problemie harmonogramowania zadań w systemach złożonych z maszynami alternatywnymi.

On the scheduling production tasks, artificial intelligence methods are widely used. One of this kind of metaheuristics are genetic algorithms. In this article is the definition of task flexible job-shop scheduling problem. Also shows selected coding methods to this problem in the genetic algorithms.