Nieklasyczne podejście ewolucyjne do problemu szeregowania zadań w systemach produkcyjnych

• Autorzy: Jardzioch A. , Skobiej B.

Warianty tytułu

EN

Non-classical Evolutionary Approach to the Job Scheduling Problem in Production Systems

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowano nieklasyczne podejście ewolucyjne, oparte na algorytmie genetycznym, do rozwiązania problemu szeregowania zadań w systemie produkcyjnym. Optymalizację szeregowania przeprowadzono względem możliwego do uzyskania zysku, z obliczaniem kar za opóźnienia. Zaproponowane podejście obejmuje permutacyjne kodowanie chromosomów, elitaryzm, brak genetycznego operatora rekombinacji, zastosowanie mutacji heurystycznej oraz zmiennej w czasie mutacji zamiennej (ang. swap mutation). Przeprowadzono badania dla 9 losowych zleceń dla których metodą całkowitego przeszukania permutacyjnego obliczono optymalne szeregowanie pod względem zysku. Uzyskane wyniki porównano z innymi metodami szeregowania.

EN

This article shows how a non-classical evolutionary approach, based on a genetic algorithm, can be used to solve the problem of task scheduling in production systems. The optimization of scheduling was done to maximize possible profit, including the calculation of delay penalties. The approach encompasses permutation encoding, elitism, lack of the genetic recombination operator, the use of heuristic mutation as well as time-variant swap mutation. For nine random orders optimal scheduling was determined using exhaustive search method. The results of the optimization were compared to those obtained with other methods of scheduling.

Słowa kluczowe

PL

szeregowanie zadań; system produkcyjny; podejście ewolucyjne; algorytm genetyczny; permutacyjne kodowanie chromosomów; elitaryzm; genetyczny operator rekombinacji; mutacja heurystycza; mutacja zamienna

EN

scheduling; production system; evolutionary approach; genetic algorithm; permutation encoding; elitism; genetic recombination operator; heuristic mutation; swap mutation

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2013
• Tom: nr 5
• Strony: 281--287, CD 2
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Jardzioch A.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

autor

Skobiej B.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Bibliografia

• [1] Chen B. et al.: A New Heuristic for Three-Machine Flow Shop Scheduling, Operations Research, vol. 44, No. 6, 1996.
• [2] Cheng R., Gen M.: Resource-constrained project scheduling problem using genetic algorithms, Intelligent Automation and Soft Computing 3: pp 273-286, 1997.
• [3] Goldberg D.E.: Alleles Loci and the TSP, Proceedings of the First International Conference on Genetic Algorithms and Their Application, Lawrence Erlbaum, New Jersey, pp 154-159, 1985.
• [4] Grajek M.: Harmonogramowanie dostaw wyrobów alkoholowych na obszarze Unii Europejskiej –rozpoznanie problemu (cz. 1), Logistyka 5/2011, Instytut Logistyki i Magazynowania, Poznań, 2011.
• [5] Jardzioch A., Skobiej B.: Petri net implementation in queue algorithms analysis for flexible manufacturing systems, Foundations of Computing and Decision Sciences, vol. 36, No. 3-4, pp 207-217, 2011.
• [6] Johnson S. M.: Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, pp 61-68, 1954.
• [7] Karger D., Stein C., Wein J.: Scheduling Algorithms, Algorithms and Theory of Computation Handbook, Chapman & Hall/CRC Publishing, 2010.
• [8] Knosala R. et al.: Zastosowania metod sztucznej inteligencji w inżynierii produkcji, Wydawnictwa Naukowo-Techniczne, Warszawa, 2002.
• [9] Lawler E.L. et al.: Sequencing and Scheduling: Algorithms and Complexity. Handbooks in Operations Research and Management Science, Vol. 4., Logistics of Production and Inventory, pp 445-522, North-Holland, 1993.
• [10] McNaughton R.: Scheduling with deadlines and loss functions. Management Science, 6:1-12, 1959.
• [11] Oliver I.M., Smith D.J., Holland J.R.C.: A Study of Permutation Crossover Operator on the TSP, Proceedings of the Second International Conference, Lawrence Erlbaum, New Jersey, pp 224-230, 1987.
• [12] Skołud B., Wosik I.: Algorytmy immunologiczne w szeregowaniu zadań produkcyjnych, Zarządzanie przedsiębiorstwem, Nr 1/2008, s.47-56, 2008.
• [13] Wang X., Xie X., Cheng T.C.E.: A modified artificial bee colony algorithm for order acceptance in twomachine flow shops. International Journal of Production Economics No. 141, 2013.
• [14] Yamamura M., Ono T., Kobayashi S.: Character-Preserving Genetic Algorithms for Traveling Salesman Problem, Journal of Japanese Society for Artificial Intelligence, Vol.7, No.6, pp 1049-1059, 1992.