Cyclic flow shop scheduling problem with two-machine cells

• Autorzy: Bożejko W. , Gnatowski A. , Idzikowski R. , Wodecki M.

Identyfikatory

DOI

10.1515/acsc-2017-0009

• Języki publikacji: EN

Abstrakty

EN

In the paper a variant of cyclic production with setups and two-machine cell is considered. One of the stages of the problem solving consists of assigning each operation to the machine on which it will be carried out. The total number of such assignments is exponential. We propose a polynomial time algorithm finding the optimal operations to machines assignment.

Słowa kluczowe

EN

job shop; cyclic scheduling; multi-machine; assignment

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2017
• Tom: Vol. 27, no. 2
• Strony: 151--167
• Opis fizyczny: Bibliogr. 11 poz., diagr., rys., wykr., wzory

Twórcy

autor

Bożejko W.

• Department of Automatics, Mechatronics and Control Systems, Faculty of Electronics, Wrocław University of Technology, Janiszewskiego 11-17, 50-372 Wrocław, Poland

autor

Gnatowski A.

• Department of Automatics, Mechatronics and Control Systems, Faculty of Electronics, Wrocław University of Technology, Janiszewskiego 11-17, 50-372 Wrocław, Poland

autor

Idzikowski R.

• Department of Automatics, Mechatronics and Control Systems, Faculty of Electronics, Wrocław University of Technology, Janiszewskiego 11-17, 50-372 Wrocław, Poland

autor

Wodecki M.

• Institute of Computer Science, University of Wrocław, Joliot-Curie 15, 50-383 Wrocław, Poland

Bibliografia

• [1] W. Bożejko, M. Uchroński and M. Wodecki: Parallel metaheuristics for the cyclic flow shop scheduling problem. Computers & Industrial Engineering, 95 (2016), 156-163.
• [2] W. Bożejko, A. Gnatowski, T. Niżyński and M. Wodecki: Tabu search algorithm with neural tabu mechanism for the cyclic job shop problem. In Artificial Intelligence and Soft Computing: 15th International Conference, ICAISC 2016, Zakopane, Poland, June 12-16, 2016, Proceedings, Part II, L. Rutkowski, M. Korytkowski, R. Scherer, R. Tadeusiewicz, L. A. Zadeh, and J. M. Zurada, Eds. Springer International Publishing, Cham, 2016, 409-418.
• [3] W. Bożejko, M. Uchroński and M. Wodecki: Multi-GPU Tabu Search Metaheuristic for the Flexible Job Shop Scheduling Problem. Springer International Publishing, Heidelberg, 2014, 43-60.
• [4] W. Bożejko and M. Wodecki: Problemy cykliczne z równoległymi maszynami (in Polish). In Automatyzacja procesów dyskretnych, Teoria i zastosowania (red. A. Świerniak, J. Krystek), A. Świerniak and J. Krystek, Eds. Gliwice, 2014, 27-36.
• [5] F. Glover: Future paths for integer programming and links to artificial intelligence. Computer & Operational Research, 13(5), (1986), 533-549.
• [6] A. Gnatowski: Benchmarks for nonpermutational flowshop with 2-machine nests and cycle time criterion. 2016. http://wojciech.bozejko.staff.iiar.pwr.wroc.pl/Benchmarks/F_cycle_nonperm/F_cycle_2machines_benchmarks.zip, Available online [2017-03-13].
• [7] A. Gnatowski: Finding properties of an assignment problem in application to cyclic scheduling problems (in Polish). Tech. Rep. PRE No. 5, Faculty of Electronics, Wrocław University of Science and Technology, 2016.
• [8] T. Kampmeyer: Cyclic Scheduling Problems. PhD thesis, University Osnabrück, 2006.
• [9] E. Levner, V. Kats, D. A. L. de Pablo and T. Cheng: Complexity of cyclic scheduling problems: A state-of-the-art survey. Computers & Industrial Engineering, 59(2), (2010), 352-361.
• [10] E. Nowicki and C. Smutnicki: A fast taboo search algorithm for the job shop problem. Management science, 42(6), (1996), 797-813.
• [11] T. Sawik: A mixed integer programming for cyclic scheduling of flexible flow lines. Bulletin of the Polish Academy of Sciences, Technical Sciences, 62(1), (2014), 121-128.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).