Heuristic algorithm for scheduling multiple-operation jobs of cyclic manufacturing processes

• Autorzy: Raszka J. , Jamroż L.

Warianty tytułu

PL

Heurystyczny algorytm planowania wielooperacyjnych zadań cyklicznych procesów produkcyjnych

• Języki publikacji: EN

Abstrakty

EN

The paper deals with the problem of evaluating the performance of job-shop systems under a cyclic manufacturing process. This process for each job is specified uniquely. Modelling based on timed event graphs terminology allows the performance of a system of repetitive production processes to be evaluated. The objective of the schedule production is to minimize the cycle time and the number of jobs that are actually required in the process. The considered problem is specified as a linear programming problem and is solved by a heuristic algorithm.

PL

rtykuł dotyczy oszacowania wydajności systemów typu job-shop, w których występują cykliczne procesy produkcyjne. Proces produkcyjny jest jednoznacznie określony dla każdego zadania. Modelowanie oparte na terminologii czasowych grafów znakowanych pozwala oszacować wydajność systemu cyklicznych procesów produkcyjnych. Celem planowania produkcji jest minimalizacja czasu cyklu i liczby zadań wymaganych w procesie. Rozważany problem przedstawiony jest jako problem programowania liniowego i rozwiązywany za pomocą algorytmu heurystycznego

Słowa kluczowe

EN

job shop; timed event graph; cycle time; performance evaluation

PL

job-shop; czasowy graf znakowany; czas cyklu; oszacowanie wydajności

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2015
• Tom: Vol. 36, nr 3
• Strony: 27--42
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Raszka J.

• Cracow University of Technology, Institute of Computer Science, Warszawska 24, 31-155 Kraków (Poland)

autor

Jamroż L.

• Cracow University of Technology, Institute of Computer Science, Warszawska 24, 31-155 Kraków (Poland)

Bibliografia

• 1. Baccelli F.L., et al.: Synchronization and Linearity. An Algebra for Discrete Event Systems. John Wiley & Sons, 1992.
• 2. Banaszak Z. (ed.): Modelling and control of FMS. Petri net approach. Wroclaw Technical University Press, 1991.
• 3. Carier J., Chretienne P.: Timed Petri net schedules. Advances in Petri nets, Rozenberg G. (ed.), LNCS, Springer Verlag, 1988.
• 4. DiCesare F. et al.: Practice of Petri Nets in Manufacturing. Chapman & Hall, 1993.
• 5. Dubois D., Stecke K. E.: Dynamic analysis of repetitive decision-free discrete event processes. The algebra of timed marked graphs and algorithmic issues. Annals of Operation Research. Volume on ”Production Planning and Scheduling”, 1990.
• 6. Gaubert S.: An algebraic method for optimizing resources in timed event graphs. Lecture Notes in Computer and Information Science, Springer Verlag, Vol. 144, 1990, p. 957÷966.
• 7. Goldin G., A.: Problem Solving Heuristics - Affect and Discrete Mathematic. European Mathematical Information Service, The Electronic Library of Mathematics – ZDM 2004, Vol. 36 (2), p. 56÷60.
• 8. Graves S. C.: A review of production scheduling. Operations Research, vol. 18, 1981, p. 841÷852.
• 9. Hartung S., Nichterlein A.: NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs. Lecture Notes in Computer Science Volume 7318, 2012, p. 283÷292.
• 10. Hillion H. P., Proth J. M.: Performance evaluation of job-shop systems using timed event graphs. IEEE Transactions on Automatic Control, Vol. 34, No.1, 1989, p. 1÷9.
• 11. Jamroż L., Raszka J.: Simulation method for the performance evaluation of system of discrete cyclic processes. Proceedings of the 16th IASTED International Conference on Modelling, Identification and Control, Innsbruck, Austria Feb. 17–19th 1997, 190÷193.
• 12. Kolahan F., Kayvanfar V.: A Heuristic Algorithm Approach for Scheduling of Multicriteria Unrelated Parallel Machine. World, Academy of Science, Engineering and Technology 59, 2009, p. 102÷105.
• 13. Kusiak A. (ed.): Modelling and design of flexible manufacturing systems. Elsevier Science Publishers, Amsterdam 1986.
• 14. Laftit S., Proth J.M., Xie X. L.: Optimization of invariant criteria for event graphs. IEEE Trasnsactions on Automatic Control, Vol. 37, No. 5, 1992, p. 547÷555.
• 15. Magott J.: Performance evaluation of computer systems using Petri nets. Scientific Papers of the Institute of Technical Cybernetics of Wroclaw Technical University, No. 80, s. Monographs 15, 1989, (in Polish).
• 16. Melnikov B.: Discrete Optimization Problems – Some New Heuristic Approaches. Eighth International Conference on High-Performance Computing in Asia-Pacific Region (HPC Asia 2005), 30 November-3 December 2005 Beijing, China.
• 17. Murata T.: Petri nets: proprties, analysis and applications. Proceedings of the IEEE, Vol. 77, No. 4, 1989, p.541÷580.
• 18. Skołud B., Wosik I.: Algorytmy ewolucyjne w szeregowaniu zadań produkcyjnych Zarządzanie Przedsiębiorstwem nr 1, 2008.
• 19. Szpyrka M.: Sieci Petriego w modelowaniu i analizie systemów współbieżnych. WNT, Warszawa 2008.
• 20. Tang L., Wang H., Li G., Xu F.: Adaptive heuristic search algorithm for discrete variables based multi-objective optimization. Springer-Verlag, Berlin Heidelberg 2013 October 2013, Volume 48, Issue 4, p. 821÷836.
• 21. Varthanana P. A., Muruganb N., Mohan Kumarc G.: A simulation based heuristic discrete particle swarm algorithm for generating integrated production–distribution plan. Applied Soft Computing Journal, Vol. 12, No. 9, p. 3034÷3050, Sept. 2012.