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

• Autorzy: Warżołek D. , Gola Ł.

Warianty tytułu

EN

Genetic algorithms in flexible job-shop scheduling problems. Genetic representations.

• Konferencja: Konferencja Naukowa „Oszczędność i efektywność – współczesne rozwiązania w logistyce i produkcji” (9 ; 19-21.11.2014 ; Będlewo, Polska)
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

algorytm; algorytm genetyczny; maszyny alternatywne

EN

algorithm; genetic algorithm

• Wydawca: Polskie Wydawnictwo Ekonomiczne SA
• Czasopismo: Gospodarka Materiałowa i Logistyka
• Rocznik: 2014
• Tom: nr 11
• Strony: 135--140
• Opis fizyczny: Bibliogr. 14 poz., rys., tab., pełny tekst na CD

Twórcy

autor

Warżołek D.

• Instytut Technologii Maszyn i Automatyzacji Produkcji, Politechnika Krakowska

autor

Gola Ł.

• Instytut Technologii Maszyn i Automatyzacji Produkcji, Politechnika Krakowska

Bibliografia

• Bierwirth Ch., A generalized permutation approach to job shop scheduling with genetic algorithms, Operations-Research-Spektrum, Vol.17, No.2-3, 1995.
• Chen H., Ihlow J., Lehmann C., A genetic algorithm for flexible job shop scheduling, Proc. IEEE International Conference on Robotics and Automation, Vol.2, 1999.
• Cheng R., Gen M., Tsujimura Y., Tutorial survey of job-shop scheduling problems using genetic algorithms - I. representation, Computers & Industrial Engineering, Vol.30, No.4, 1996.
• Cheng R., Gen M., Tsujimura Y., A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies, Computers & Industrial Engineering, Vol.36, No.2, 1999.
• Fattahi P., Mehrabad M.S., Jolai F., Mathematical modeling and heuristic approaches to flexible job shop scheduling problems, Journal of Intelligent Manufacturing, Vol.18, No.3, 2007.
• Gao J., Gen M., Sun L., Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm, Journal of Intelligent Manufacturing, Vol.17, No.4, 2006.
• Ho N.B., Tay J.C., GENACE: an efficient cultural algorithm for solving the flexible job-shop problem, IEEE Congress on Evolutionary Computation, Vol.2, 2004.
• Kacem, I., Hammadi, S., Borne P., Approach by localization and multi objective evolutionary optimization for flexible job-shop scheduling problems, IEEE Transactions on Systems, Man, and Cybernetics, Part C, Vol.32, No.1, 2002.
• Mesghouni K., Application des algorithmes evolutionnistes dans les problemes d'optimisation en ordonnancement de la production, PhD dissertation, Lille 1 University, France, 1999.
• Mesghouni K., Hammadi S., Borne P., Evolutionary algorithms for job shop scheduling, Proc. International Journal of Applied Mathematics and Computer Science, Vol.14, No.1, 2004.
• Pawlak M., Algorytmy ewolucyjne jako narzędzie harmonogramowania produkcji, Wydawnictwo Naukowe PWN, Warszawa, 1999.
• Pezzella F., Morganti G., Ciaschetti G., A genetic algorithm for the flexible job shop scheduling problem, Computers and Operations Research, Vol.35, No.10, 2008.
• Sergienko I.V., Hulianytskyi L.F., Sirenko S.I., Classification of applied methods of combinatorial optimization, Cybernetics and Systems Analysis, Vol.45, No.5, 2009.
• Tay J.C., Wibowo D., An effective chromosome representation for evolving flexible job shop schedules, Lecture Notes in Computer Science, Vol.3101, 2004.