Abstract
Due-date determination problems have gained significant attention in recent years due to the industrial focus in the just-in-time philosophy. This paper considers a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence, both earliness and tardiness should be penalized. It is assumed that earliness and tardiness (ET) penalties will not occur if a job is completed within the due window. However, ET penalties will occur if a job is completed outside the due window. The objective is to determine a schedule that minimizes sum of the earliness and tardiness of jobs. To achieve this objective, three hybrid metaheuristics are proposed. The first metaheuristic is a hybrid algorithm which combines elements from both simulated annealing (SA) as constructive heuristic search and a variable neighborhood search (VNS) as local search improvement technique. The second one presents a hybrid metaheuristic algorithm which composed of a population generation method based on an ant colony optimization (ACO) and a VNS to improve the population. Finally, a hybrid metaheuristic approach is proposed which integrates several features from ACO, SA, and VNS in a new configurable scheduling algorithm. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. Computational experiments conducting on 252 randomly generated problems compare the results with the VNS algorithm proposed previously and show that the procedure is capable of producing consistently good results.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aarts E, Lenstra JK (1997) Search in combinatorial optimization. Wiley, New York
Ahmed MU, Sundararaghavan PS (1990) Minimizing the weighted sum of late and early completion penalties in a single machine. IIE Trans 22(3):288–290. doi:10.1080/07408179008964183
Ahuja RK, Ergun O, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl Math 123:75–102. doi:10.1016/S0166-218X(01)00338-9
Almeida MT, Centeno M (1998) A composite heuristic for the single machine early/tardy job scheduling problem. Comput Oper Res 25:625–635. doi:10.1016/S0305-0548(97)00097-X
Anger FD, Lee CY, Martin-Vega LA (1986) Single-machine scheduling with tight windows. Research Paper, 86–16, University of Florida
Anghinolfi D, Paolucci M (2007) Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Comput Oper Res 34:3471–3490. doi:10.1016/j.cor.2006.02.009
Balakrishnan N, Kanet JJ, Sridharan SV (1999) Early/tardy scheduling with sequence-dependent setups on uniform parallel machines. Comput Oper Res 26:127–141. doi:10.1016/S0305-0548(98)00051-3
Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6(2):154–160
Bilge U, Kirac F, Kurtulan M, Pekgun PA (2004) Tabu search algorithm for parallel machine total tardiness problem. Comput Oper Res 31:397–414. doi:10.1016/S0305-0548(02)00198-3
Birman M, Mosheiov G (2004) A note on a due-date assignment on a two-machine flow-shop. Comput Oper Res 31:473–480. doi:10.1016/S0305-0548(02)00225-3
Bülbül K, Kaminsky P, Yano C (2007) Preemption in single machine earliness/tardiness scheduling. J Sched 10:271–292. doi:10.1007/s10951-007-0028-6
Chang P-C, Chen S-H, Fan C-Y (2008) A hybrid electromagnetism-like algorithm for single machine scheduling problem. Expert Syst Appl 36:1259–1267. doi:10.1016/j.eswa.2007.11.050
Chen ZL (1996) Scheduling and common due date assignment with earliness–tardiness penalties and batch delivery costs. Eur J Oper Res 93:49–60. doi:10.1016/0377-2217(95)00133-6
Chen ZL, Lee CY (2002) Parallel machine scheduling with a common due window. Eur J Oper Res 136:512–527. doi:10.1016/S0377-2217(01)00068-6
Chen ZL, Powell WB (1999) A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. Eur J Oper Res 116:221–233
Cheng TCE, Chen ZL (1994) Parallel-machine scheduling with earliness and tardiness penalties. J Oper Res Soc 45:685–695
Dorigo M, Stuetzle T (2004) Ant colony optimization. MIT, Boston, MA
Emmons H (1987) Scheduling to a common due-date on parallel uniform processors. Nav Res Logistics Q 34:803–810. doi:10.1002/1520-6750(198712)34:6<803::AID-NAV3220340605>3.0.CO;2-2
Esteve B, Aubijoux C, Chartier A, Tkindt V (2006) A recovering beam search algorithm for the single machine just-in-time scheduling problem. Eur J Oper Res 172:798–813. doi:10.1016/j.ejor.2004.11.014
Federgruen A, Mosheiov G (1997) Heuristics for multi-machine min–max scheduling problems with general earliness and tardiness costs. Nav Res Logistics 44:287–299. doi:10.1002/(SICI)1520-6750(199704)44:3<287::AID-NAV4>3.0.CO;2-4
Feng G, Lau HC (2005) Efficient algorithms for machine scheduling problems with earliness and tardiness penalties. In: Proceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications, New York, USA, July 18–21, 2005, pp 196–211
Fowler JW, Horng SM, Cochran JK (2003) A hybridized genetic algorithm to solve parallel machine scheduling problems with sequence-dependent setups. Int J Ind Eng Theory Appl Pract 10:232–243
Gajpal Y, Rajendran C (2006) An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops. Int J Prod Econ 101:259–272. doi:10.1016/j.ijpe.2005.01.003
Gendreau M, Laporte G, Guimaraes EM (2001) A divide and merge heuristic for the multiprocessor scheduling problem with sequence-dependent setup times. Eur J Oper Res 133:183–189. doi:10.1016/S0377-2217(00)00197-1
Gordon V, Proth JM, Chu C (2002) A survey of the state-of-the-art of common due-date assignment and scheduling research. Eur J Oper Res 135:1–25. doi:10.1016/S0377-2217(01)00181-3
Hansen P, Mladenovic N, Dragan U (2004) Variable neighborhood search for the maximum clique. Discrete Appl Math 145(1):117–125. doi:10.1016/j.dam.2003.09.012
Heady RB, Zhu Z (1998) Minimizing the sum of job earliness and tardiness in a multimachine system. Int J Prod Res 36:1619–1632. doi:10.1080/002075498193192
Herrmann JW, Lee CY (1993) On scheduling to minimize earliness–tardiness and batch delivery costs with a common due date. Eur J Oper Res 70:272–288. doi:10.1016/0377-2217(93)90239-J
Hiraishi K, Levner E, Vlach M (2002) Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs. Comput Oper Res 29:841–848. doi:10.1016/S0305-0548(00)00086-1
Hoogeveen JA (2005) Multicriteria scheduling. Eur J Oper Res 167:592–623. doi:10.1016/j.ejor.2004.07.011
Janiak A, Kozan E, Lichtenstein M, Oguz C (2007) Metaheuristic approaches to the hybrid flowshop scheduling problem with a cost-related criterion. Int J Prod Econ 105:407–424. doi:10.1016/j.ijpe.2004.05.027
Kim D, Kim K, Jang W, Chen F (2002) Unrelated parallel machine scheduling with setup times using simulated annealing. Comput Integr Manuf 18:223–231. doi:10.1016/S0736-5845(02)00013-3
Kima DW, Na DG, Chenb FF (2003) Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. Comput Integr Manuf 19:173–181. doi:10.1016/S0736-5845(02)00077-7
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680. doi:10.1126/science.220.4598.671
Kramer FJ, Lee CY (1994) Due window scheduling for parallel machines. Math Comput Model 20:69–89. doi:10.1016/0895-7177(94)90208-9
Kubiak W, Lou S, Sethi R (1990) Equivalence of mean flow time problems and mean absolute deviation problems. Oper Res Lett 9:371–374. doi:10.1016/0167-6377(90)90056-B
Kurz ME, Askin RG (2001) Heuristic scheduling of parallel machines with sequence-dependent setup times. Int J Prod Res 39:3747–3769. doi:10.1080/00207540110064938
Lam K, Xing W (1997) New trends in parallel machine scheduling. Int J Oper Manage 17:326–338. doi:10.1108/01443579710159932
Lauff V, Werner F (2004) Scheduling with common due date, earliness and tardiness penalties for multimachine problems: a survey. Math Comput Model 40:637–655. doi:10.1016/j.mcm.2003.05.019
Lee CY, Danusaputro S, Lin CS (1991) Minimizing weighted number of tardy jobs and weighted earliness–tardiness penalties about a common due date. Comput Oper Res 18:379–389. doi:10.1016/0305-0548(91)90098-C
Lenstra J, Rinnooy Kan A, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrete Math 1:343–362. doi:10.1016/S0167-5060(08)70743-X
Logendrana R, Mcdonellb B, Smuckera B (2007) Scheduling unrelated parallel machines with sequence-dependent setups. Comput Oper Res 11:3420–3438. doi:10.1016/j.cor.2006.02.006
Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097–1100. doi:10.1016/S0305-0548(97)00031-2
Montgomery DC (2000) Design and analysis of experiments, 5th edn. Wiley, New York
Nessah F, Yalaoui F, Chu C (2005) New heuristics for identical parallel machine scheduling with sequence-dependent setup times and dates. In: Proceedings of the International Conference on Industrial Engineering and Systems Management, Marrakech, Morocco, May 16–19, 2005, pp 32–41
Park Y, Kim S, Lee YH (2000) Scheduling jobs on parallel machines applying neural network and heuristic rules. Comput Ind Eng 38:189–202. doi:10.1016/S0360-8352(00)00038-3
Pinedo M (1995) Scheduling theory, algorithms, and systems. Prentice-Hall, Englewood Cliffs, NJ
Radhakrishnan S, Ventura JA (2000) Simulated annealing for parallel machine scheduling with earliness–tardiness penalties and sequence-dependent setup times. Int J Prod Res 38:2233–2252. doi:10.1080/00207540050028070
Rios-Mercado RZ, Bard JF (1998) Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. Comput Oper Res 25(5):351–366. doi:10.1016/S0305-0548(97)00079-8
Rocha M, Gómez Ravetti M, Mateus GR, Pardalos PM (2007) Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighborhood search. IMA J Manage Math 18:101–115. doi:10.1093/imaman/dpm016
Sivrikaya-Serifoglu F, Ulusoy G (1999) Parallel machine scheduling with earliness and tardiness penalties. Comput Oper Res 26:773–787. doi:10.1016/S0305-0548(98)00090-2
Stützle T (1998) An ant approach for the flowshop problem. In: Zimmerman H (ed) Proceedings of the Sixth European Congress on Intelligent Techniques and Soft Computing (EUFIT‘98), vol 3. Mainz, Aachen, Germany, pp 1560–1564
Tahar DN, Yalaoui F, Chu C, Amodeo L (2006) A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times. Int J Prod Econ 99:63–73. doi:10.1016/j.ijpe.2004.12.007
Talbi E (2002) A taxonomy of hybrid metaheuristics. J Heuristics 8(5):541–564. doi:10.1023/A:1016540724870
Tamimi SA, Rajan VN (1997) Reduction of total weighted tardiness on uniform machines with sequence-dependent setups. In: Proceedings of the 6th Industrial Engineering Research Conference, pp 181–185
Tasgetiren MF, Sevkli M, Liang YC, Gencyilmaz G (2007) Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flowshop sequencing problem. Eur J Oper Res 177(3):1930–1947. doi:10.1016/j.ejor.2005.12.024
Tian P, Ma J, Zhang DM (1999) Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property: an investigation of generation mechanism. Eur J Oper Res 118:81–94. doi:10.1016/S0377-2217(98)00308-7
Vignier A, Sonntag B, Portmann MC (1999) Hybrid method for a parallel-machine scheduling problem. In: IEEE Symposium on Emerging Technologies and Factory Automation, ETFA, 1, 671–678
Wan G, Yen BPC (2002) Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. Eur J Oper Res 142:271–281. doi:10.1016/S0377-2217(01)00302-2
Yao X (1995) A new simulated annealing algorithm. Int J Comput Math 56:161–168. doi:10.1080/00207169508804397
Yeung WK, Oğuz C, Cheng TCE (2004) Two-stage flowshop earliness and tardiness machine scheduling involving a common due window. Int J Prod Econ 90:421–434. doi:10.1016/S0925-5273(03)00044-6
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Behnamian, J., Zandieh, M. & Fatemi Ghomi, S.M.T. Due window scheduling with sequence-dependent setup on parallel machines using three hybrid metaheuristic algorithms. Int J Adv Manuf Technol 44, 795–808 (2009). https://doi.org/10.1007/s00170-008-1885-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-008-1885-7