Minimal cycle time determination and golf neighborhood generation for the cyclic flexible job shop problem

• Autorzy: Bożejko W. , Pempera J. , Wodecki M.

Identyfikatory

DOI

10.24425/123440

• Języki publikacji: EN

Abstrakty

EN

In the paper, a problem of scheduling operations in the cyclic flexible job shop system is considered. A new, very fast method of determining the cycle time for any order of tasks on machines is also presented. It is based on the analysis of the paths in the graph representing the examined problem. The theorems concerning specific properties of the graph are proven and used in the construction of the heuristic algorithm searching the solutions space by using the so-called golf neighborhood, which is generated in a way similar to the game of golf, which helps to intensify and diversify calculations. The conducted computational experiments fully confirmed the effectiveness of the proposed method. The proposed methods and properties can be adapted and used in the construction of local search algorithms for solving many other optimization problems.

Słowa kluczowe

EN

cyclic scheduling; metaheuristic; discrete optimization

PL

planowanie cykliczne; metaheurystyka; dyskretna optymalizacja

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2018
• Tom: Vol. 66, nr 3
• Strony: 333--344
• Opis fizyczny: Bibliogr. 21 poz., rys., wykr., tab.

Twórcy

autor

Bożejko W.

• Department of Automatics, Mechatronics and Control Systems Faculty of Electronics, Wrocław University of Science and Technology, Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Pempera J.

• Department of Automatics, Mechatronics and Control Systems Faculty of Electronics, Wrocław University of Science and Technology, Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Wodecki M.

• Telecommunications and Teleinformatics Department, Faculty of Electronics Wrocław University of Science and Technology, Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• [1] J.W. Barnes and J.B. Chambers, “Flexible job shop scheduling by tabu search”, Graduate program in operations research and industrial engineering The University of Texas at Austin, Technical Report Series, ORP96‒09 (1996).
• [2] W. Bożejko, M. Uchroński, and M. Wodecki, “The new golf neighborhood for the flexible job shop problem”, Procedia Computer Science 1, 289–296 (2010).
• [3] W. Bożejko, M. Uchroński, and M. Wodecki, “Parallel metaheuristics for the flexible job shop problem”, Lecture Notes in Artificial Intelligence 6114, 395–402 (2010).
• [4] W. Bożejko, M. Uchroński, and M. Wodecki, “Parallel hybrid metaheuristics for the flexible job shop problem”, Computers and Industrial Engineering 59, 323–333 (2010).
• [5] W. Bożejko, M. Uchroński, and M. Wodecki, “Solving the flexible job shop problem on multi GPU”, Procedia Computer Science 9, 2020–2023 (2012).
• [6] W. Bożejko, J. Pempera, and M. Wodecki, “Parallel simulated annealing algorithm for cyclic flexible job shop scheduling problem”, Lecture Notes in Artificial Intelligence 9120, 603– 612 (2015).
• [7] P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search”, Annals of Operations Research 41, 157–183 (1993).
• [8] P. Brucker and T. Kampmeyer, “Cyclic job shop scheduling problems with blocking”, Annals of Operations Research 159, 161– 181 (2008).
• [9] P. Brucker and T. Kampmeyer, “A general model for cyclic machine scheduling problems”, Discrete Applied Mathemathics 156, 13 2561–2572 (2008).
• [10] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and S. Clifford, Introduction to Algorithms, MIT Press and McGraw-HilL, Second Edition, MIT Press and McGraw-Hill, 2001.
• [11] J. Grabowski and J. Pempera, “New block properties for the permutation flow shop problem with application in tabu search”, Journal of Operational Research Society 52, 210–220 (2001).
• [12] L. Houssin, “Cyclic jobshop problem and (max,plus) algebra”, World IFAC Congress, Milan, 2717–2721 (2011).
• [13] E. Hurink, B. Jurisch, and M. Thole, “Tabu search for the job shop scheduling problem with multi-purpose machines”, Operations Research Spektrum 15, 205–215 (1994).
• [14] H.Z. Jia, A.Y.O. Nee, J.Y.H. Fuh, and Y.F. Zhang, “A modified genetic algorithm for distributed scheduling problems”, International Journal of Intelligent Manufacturing 14, 351–362 (2003).
• [15] I. Kacem, S. Hammadi, and R. Borne, “Approach by localization and multiobjective evolutionary optimization for flexible job shop scheduling problems”, IEEE Transactions on Systems, Man, and Cybernetics Part C 32(1), 1–13 (2002).
• [16] T. Kampmeyer, “Cyclic scheduling problems”, Ph. D. Thesis, University Osnabriick (2006).
• [17] M. Mastrolilli and L.M. Gambardella, “Effective neighborhood functions for the flexible job shop problem”, Journal of Scheduling 3(1), 3–20 (2000).
• [18] E. Nowicki and C. Smutnicki, “A fast tabu search algorithm for permutation flow shop problem”, European Journal of Operational Research 91, 160–175 (1996).
• [19] M. Wodecki, “A block approach to earliness-tardiness scheduling problems”, International Journal on Advanced Manufacturing Technology 40, 797–807 (2009).
• [20] T. Sawik, “A mixed integer program for cyclic scheduling of flexible flow lines”, Bull. Pol. Ac.: Tech. 62(1), 121–128 (2014).
• [21] W. Xia and Z. Wu, “An effective hybrid optimization approach for multiobjective flexible job shop scheduling problem”, Computers and Industrial Engineering 48, 409–25 (2005).

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).