Minimizing total tardiness in no-wait flowshops

• Autorzy: Aldowaisan T. , Allahverdi A.
• Języki publikacji: EN

Abstrakty

EN

We address the m-machine no-wait flowshop scheduling problem where the objective is to minimize total tardiness. To the best of our knowledge, the considered problem has not been addressed so far. We propose heuristic solutions since the problem is NP-hard. Initially, we consider a number of dispatching rules commonly used for the considered objective in other scheduling environments. We identify through computational experiments the best performing dispatching rule and then propose simulated annealing (SA) and genetic algorithms (GA) by using the best performing dispatching rule as an initial solution. This achieves at least 50% improvement in the SA and GA performances. Next, we propose enhanced versions of SA and GA and show through computational experiments that the enhanced versions provide over 90% further improvement. The performance of enhanced GA is slightly better than that of enhanced SA however, the computation time of enhanced GA is about 10 times that of enhanced SA. Therefore, we conclude that the enhanced SA outperforms the enhanced GA.

Słowa kluczowe

EN

no-wait flowshop; scheduling; flowshop; total tardiness

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2012
• Tom: Vol. 37, No. 3
• Strony: 149--162
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Aldowaisan T.

• Department of Industrial and Management Systems Engineering, College of Engineering and Petroleum, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait, Fax: [phone]

autor

Allahverdi A.

• Department of Industrial and Management Systems Engineering, College of Engineering and Petroleum, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait, Fax: [phone]

Bibliografia

• [1] Aldowaisan, T., and Allahverdi, A. No-wait flowshop scheduling problem to minimize the number of tardy Jobs. International Journal of Advanced Manufacturing Technology 2012 (to appear).
• [2] Aldowaisan T, Allahverdi A. A new heuristic for m-machine no-wait flowshop to minimize total completion time. OMEGA International Journal of Management Sciences 2004; 32: 345-352.
• [3] Aldowaisan T, Allahverdi A. New heuristics for no-wait flowshops to minimize makespan. Computers & Operations Research 2003; 30: 1219-1231.
• [4] Allahverdi A, Aldowaisan T. No-wait flowshops with bicriteria of makespan and maximum lateness. European Journal of Operational Research 2004; 152: 132-147.
• [5] Allahverdi A, Aldowaisan T. No-wait flowshops with bicriteria of makespan and total completion time. Journal of the Operational Research Society 2002; 53: 1004-1015.
• [6] Allahverdi, A., Gupta, J.N.D., and Aldowaisan, T. A review of scheduling research involving setup considerations. OMEGA International Journal of Management Sciences 1999; 27: 219-239.
• [7] Allahverdi, A., Ng, C.T., Cheng, T.C.E., and Kovalyov, M.Y. A survey of scheduling problems with setup times or costs. European Journal of Operational Research 2008; 187: 985-1032.
• [8] Chang JL, Gong DW, Ma XP. A heuristic genetic algorithm for no-wait flowshop scheduling problem. Journal of China University of Mining and Technology 2007; 17: 582-586.
• [9] Chen CL, Neppalli RV, Aljaber N. Genetic Algorithms Applied to the Continuous Flow Shop Problem. Computers & Industrial Engineering 1996; 30: 919-929.
• [10] Framinan JM, Nagano MS. Evaluating the performance for makespan minimization in no-wait flowshop sequencing. Journal of Materials Processing Technology 2008; 197: 1-9.
• [11] Framinan, J.M., Leisten, R. Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm. International Journal of Production Research 2008; 46: 6479-6498.
• [12] Hall NG, Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process. Operations Research 1996; 44: 510-525.
• [13] Lenstra JK, Rinnooy Kan, AHG., Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics 1977; 1: 343-362.
• [14] Nawaz M, Enscore E, Ham I. A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. OMEGA International Journal of Management Science 1983; 11: 91-95.
• [15] Pan QK, Tasgetiren MF, Liang YC. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers & Operations Research 2008; 35: 2807-2839.
• [16] Pinedo M (1995) Scheduling; theory, algorithms, and systems. Prentice Hall, Englewood Cliffs, New Jersey.
• [17] Vallada, E., Ruiz, R. Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. OMEGA International Journal of Management Science 2010; 38: 57-67.
• [18] Vallada, E., Ruiz, R., Minella, G. Minimizing total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics. Computers and Operations Research 2008; 35: 1350-1373.
• [19] Warburton RDH. EOQ extensions exploiting the Lambert W function. European Journal of Industrial Engineering 2009; 3: 45-69.