Blocks for two-machines total weighted tardiness flow shop scheduling problem

• Autorzy: Bożejko W. , Uchroński M. , Wodecki M.

Identyfikatory

DOI

10.24425/bpasts.2020.131829

• Języki publikacji: EN

Abstrakty

EN

The paper discusses a two-machine flow shop problem with minimization of the sum of tardiness costs, being a a generalization of the popular NP-hard single-machine problem with this criterion. We propose the introduction of new elimination block properties allowing for accelerating the operation of approximate algorithms of local searches, solving this problem and improving the quality of solutions determined by them.

Słowa kluczowe

EN

flow shop; two machine; due date; minimal costs; blocks of tasks; parallel algorithm

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2020
• Tom: Vol. 68, nr 1
• Strony: 31--41
• Opis fizyczny: Bibliogr. 36 poz., rys., tab.

Twórcy

autor

Bożejko W.

• Department of Control Systems and Mechatronics, Faculty of Electronics, Wrocław University of Science and Technology

autor

Uchroński M.

• Department of Control Systems and Mechatronics, Faculty of Electronics, Wrocław University of Science and Technology

autor

Wodecki M.

• Department of Telecommunications and Teleinformatics, Faculty of Electronics, Wrocław University of Science and Technology

Bibliografia

• [1] M.-H. Ahmadi-Darani, G. Moslehi, and M. Reisi-Nafchi, “A two-agent scheduling problem in a two-machine flow-shop”, International Journal of Industrial Engineering Computations 9 (3), 289–306 (2018).
• [2] M. Al-Salem, L.B. Valencia, and G. Rabadi, “Heuristic and Exact Algorithms for the Two-Machine Just in Time Job Shop Scheduling Problem”, Mathematical Problems in Engineering 5, 1–11 (2016).
• [3] M.A.A. Ardakan, K.S. Beheshti, H. Mirmohammadi, and H.D. Ardakani, “A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem”, Numerical Algebra, Control & Optimization 7 (4), 465–480 (2017).
• [4] M. Bank, S.M. Fatemi, T. Ghomi, F. Jolai, and J. Behnamian, “Two-machine flow shop total tardiness scheduling problem with deteriorating jobs”, Applied Mathematical Modelling 36 (11), 5418–5426 (2012).
• [5] W. Bożejko, J. Grabowski, and M. Wodecki, “Block approach tabu search algorithm for single machine total weighted tardiness problem”, Computers & Industrial Engineering 50 (1-2), 1–14 (2006).
• [6] W. Bożejko, M. Uchroński, and M. Wodecki, “Parallel metaheuristics for the cyclic flow shop scheduling problem”, Computers & Industrial Engineering, 95, 156–163 (2016).
• [7] W. Bożejko, A. Gnatowski, R. Idzikowski, and M. Wodecki, “Cyclic flow shop scheduling problem with two-machine cells”, Archives of Control Sciences 27 (2), 151–168 (2017).
• [8] W. Bożejko, J. Pempera, and M. Wodecki , “Minimal cycle time determination and golf neighborhood generation for the cyclic flexible job shop problem”, Bull. Pol. Ac.: Tech. 66 (3), 333–344 (2018).
• [9] R.L. Bulfin and R. Hallah, “Minimizing the weighted number of tardy jobs on two-machineflow shop”, Computers & Operations Research 30, 1887–1900 (2003).
• [10] S.-R. Cheng, Y. Yunqiang, Ch.-H. Wen, W.-Ch. Lin, Ch.-Ch. Wu, and J. Liu, “A two-machine flowshop scheduling problem with precedence constraint on two jobs”, Soft Computing – A Fusion of Foundations, Methodologies and Applications 21 (8), 2091–2103 (2017).
• [11] R. Cole, “Parallel merge sort”, SIAM J. Comput. 17 (4), 770–785 (1988).
• [12] J. Grabowski and M. Wodecki, “A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion”, Computers and Operations Research 31, 1891–1909 (2004).
• [13] L.R. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy-Kan, “Optimization and approximation in deterministic sequencing and scheduling: A survey”, Annals of Discrete Mathematics 5, 287–326 (1979).
• [14] J.N.D. Gupta and A.M.A. Hariri, “Two-machine flowshop scheduling to minimize the number of tardy jobs”, Journal of the Operational Research Society 48, 212–220 (1997).
• [15] I. Hamdi, A. Oulamara and T. Loukil, “A branch and bound algorithm to minimise the total tardiness in the two-machine permutation flowshop scheduling problem with minimal time lags”, International Journal of Operational Research 23 (4), 387–405 (2015).
• [16] S. Hanafi, “On the Convergence of Tabu Search”, Journal of Heuristics 7, 47—58 (2000).
• [17] S.M. Johnson, “Optimal two- and three-stage production schedules with setup times included”, Naval Res. Logist. Quart. I, 61–68 (1954).
• [18] M. Khalili and R. Tavakkoli-Moghaddam, “A multi-objective electromagnetism algorithm for a bi-objective flow-shop scheduling problem”, Journal of Manufacturing Systems, 31 (2), 232–239 (2012).
• [19] M. Kharbeche and M. Haouari, “MIP models for minimizing total tardiness in a two-machine flow shop”, The Journal of the Operational Research Society 64 (5), 690–707 (2013).
• [20] C. Koulamus, “The total tardiness problem: review and extensions”, Operations Research 42, 1025–1041 (1994).
• [21] J.-Y. Lee and Y.-D. Kim, “Minimizing total tardiness in a two-machine flowshop scheduling problem with availability constraint on the first machine”, Computers & Industrial Engineering 114, 22–30 (2017).
• [22] J.K. Lenstra, A.G.H. Rinnoy Kan and P. Brucker, “Complexity of Machine Scheduling Problems”, Annals of Discrete Mathematics 1, 343–362 (1977).
• [23] B.M.T. Lin, “Scheduling in the two-machine flowshop with due date constraints”, International Journal Production Economics 70, 117–123 (2001).
• [24] A. Moukrim, D. Rebaine, and M. Serairi, “A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays”, RAIRO-Oper. Res. 48, 235–254 (2014).
• [25] M. Nawaz, E.E. Enscore, and I. Ham, “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem”, OMEGA 11 (1), 91–95 (1983).
• [26] E. Nowicki and C. Smutnicki, “A Fast tabu serach algorithm for permutation flow shop problem”, European Journal of Operational Research 91, 160–175 (1996).
• [27] C.N. Potts and L.N. Van Wassenhove, “A decomposition algorithm for the single machine total tardiness problem”, Operations Research Letters 1, 177–181 (1982).
• [28] J. Schaller, “Note on minimizing total tardiness in a two-machine flowshop”, Computers & Operations Research 32 (12), 3273–3281 (2005).
• [29] W.E. Smith, “Various Optimizers for Single-Stage Production”, Naval Research Logistics Quarterly 3 (1-2), 59–66 (1956).
• [30] Q.C. Ta, J.-C. Billaut, and J.-L. Bouquard, “Recovering beam search and Matheuristic algorithms for the F2|| ∑ Tj scheduling problem”, In 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (2013), France.
• [31] E. Taillard, “Benchmarks for basic scheduling problems”, European Journal of Operational Research 64, 278–285 (1993).
• [32] M. Uchroński, “Benchmark files for 2FP# ∑wiTi” (2018), https://zasobynauki.pl/zasoby/51102/
• [33] E. Vallada, R. Ruiz, and J. Framinan, “New hard benchmark for flowshop scheduling problems minimising makespan”, European Journal of Operational Research 240, 666–677 (2015).
• [34] S. Voß, “Tabu search: Applications and prospects”, in: Network Optimization Problems (D.Z. Du and P.M. Pardalos, eds.), World Scientific Publishing Co., Singapore, 333–353 (1993).
• [35] M. Wodecki, “A branch-and-bound parallel algorithm for single-machine total weighted tardiness problem”, International Journal of Advanced Manufacturing Technology 37 (9-10), 996–1004 (2008).
• [36] M. Wodecki, “A block approach to earliness-tardiness scheduling problems”, International Journal of Advanced Manufacturing Technology 40 (7-8), 797–807 (2009).

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).