Abstract
The unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times in the presence of due date constraints represents an important but relatively less-studied scheduling problem in the literature. In this study, a simple iterated greedy (IG) heuristic is presented to minimize the total tardiness of this scheduling problem. The effectiveness and efficiency of the proposed IG heuristic are compared with existing algorithms on a benchmark problem dataset used in earlier studies. Extensive computational results indicate that the proposed IG heuristic is capable of obtaining significantly better solutions than the state-of-the-art algorithms on the same benchmark problem dataset with similar computational resources.
Similar content being viewed by others
References
Ying KC, Lin SW (2007) Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems. Int J Adv Manuf Technol 33:793–802
McNaughton R (1959) Scheduling with deadlines and loss functions. Manage Sci 6:1–12
Lee ZJ, Lin SW, Ying KC (2009) Scheduling jobs on dynamic parallel machines with sequence-dependent setup times. Int J Adv Manuf Technol. doi:10.1007/s00170-009-2203-8
Cheng TCE, Sin CCS (1990) A state-of-the-art review of parallel-machine scheduling research. Eur J Oper Res 47:271–292
Chen JF (2005) Unrelated parallel machine scheduling with secondary resource constraints. Int J Adv Manuf Technol 26:285–292
Pfund M, Fowler JW, Gupta JND (2004) A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems. J Chin Inst Ind Eng 21:230–241
Lin SW, Chou SY, Ying KC (2007) A sequential exchange approach for minimizing earliness–tardiness penalties of single-machine scheduling with a common due date. Eur J Oper Res 177:1294–1301
Lin SW, Ying KC (2007) Solving single machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics. Int J Adv Manuf Technol 34:1183–1190
Lancia G (2000) Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan. Eur J Oper Res 120:277–288
Liaw CF, Lin YK, Chen CY, Chen M (2003) Scheduling unrelated parallel machines to minimize total weighted tardiness. Comput Oper Res 30:1777–1789
Helal M, Rabadi G, Al-Salem A (2006) A Tabu search algorithm to minimize the makespan for the unrelated parallel machines scheduling problem with setup times. Int J Oper Res 3:182–192
Shim SO, Kim YD (2007) Minimizing total tardiness in an unrelated parallel-machine scheduling problem. J Oper Res Soc 58:346–354
Rocha PL, Ravetti MG, Mateus GR, Pardalos PM (2008) Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Comput Oper Res 35:1250–1264
Ying KC, Lin SW, Lee ZJ (2009) Hybrid-directional planning: improving improvement heuristics for scheduling resource-constrained projects. Int J Adv Manuf Technol 41:358–366
Suresh V, Chaudhuri D (1994) Minimizing maximum tardiness for unrelated parallel machines. Int J Prod Econ 34:223–229
Adamopoulos GI, Pappis CP (1998) Scheduling under a common due-date on parallel unrelated machines. Eur J Oper Res 105:494–501
Kim DW, Kim KH, Jang W, Chen FF (2002) Unrelated parallel machine scheduling with setup times using simulated annealing. Robot Comput-Integr Manuf 18:223–231
Kim DW, Na DG, Chen FF (2003) Unrelated parallel machine scheduling with setup times and total weighted tardiness objective. Robot Comput-Integr Manuf 19:173–181
Chen JF (2006) Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups. Int J Adv Manuf Technol 29:557–563
Logendran R, Subur F (2004) Unrelated parallel machine scheduling with job splitting. IIE Trans 36:359–371
Logendrana R, McDonellb B, Smucker B (2007) Scheduling unrelated parallel machines with sequence-dependent setups. Comput Oper Res 34:3420–3438
Zhang Z, Zheng L, Weng MX (2007) Dynamic parallel machine scheduling with mean weighted tardiness objective by Q-Learning. Int J Adv Manuf Technol 34:968–980
Chen JF (2009) Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints. Int J Adv Manuf Technol 44:1204–1212
Chen CL, Chen CL (2009) Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times. Int J Adv Manuf Technol 43:161–169
Pinedo M (2008) Scheduling, theory, algorithms, and systems, 3rd edn. Prentice Hall, New York
Koulamas C (1994) The total tardiness problem review and extensions. Oper Res 142:764–775
Jacobs LW, Brusco MJ (1995) A local-search heuristic for large set-covering problems. Nav Res Logist 42:1129–1140
Marchiori E, Steenbeek A (2000) An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling. Lect Notes Comput Sci 1803:367–381
Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033–2049
Baraz D, Mosheiov G (2008) A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time. Eur J Oper Res 184:810–813
Ruiz R, Stützle T (2008) An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. Eur J Oper Res 187:1143–1159
Ying KC (2008) Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic. Int J Adv Manuf Technol 38:348–354
Ying KC (2009) An iterated greedy heuristic for multistage hybrid flowshop scheduling problems with multiprocessor tasks. J Oper Res Soc 60:810–817
Ying KC, Lin SW, Huang CY (2009) Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Syst Appl 36:7087–7092
Ying KC, Cheng HM (2010) Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristic. Expert Syst Appl 37:2848–2852
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lin, SW., Lu, CC. & Ying, KC. Minimization of total tardiness on unrelated parallel machines with sequence- and machine-dependent setup times under due date constraints. Int J Adv Manuf Technol 53, 353–361 (2011). https://doi.org/10.1007/s00170-010-2824-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-010-2824-y