Skip to main content
SpringerLink
Log in

Due window scheduling with sequence-dependent setup on parallel machines using three hybrid metaheuristic algorithms

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aarts E, Lenstra JK (1997) Search in combinatorial optimization. Wiley, New York

    MATH  Google Scholar 

  2. 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

    Article  Google Scholar 

  3. 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

    Article  MATH  MathSciNet  Google Scholar 

  4. 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

    Article  MATH  Google Scholar 

  5. Anger FD, Lee CY, Martin-Vega LA (1986) Single-machine scheduling with tight windows. Research Paper, 86–16, University of Florida

  6. 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

    Article  MATH  MathSciNet  Google Scholar 

  7. 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

    Article  MATH  MathSciNet  Google Scholar 

  8. Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6(2):154–160

    MATH  Google Scholar 

  9. 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

    Article  MATH  Google Scholar 

  10. 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

    Article  MATH  MathSciNet  Google Scholar 

  11. 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

    Article  MathSciNet  Google Scholar 

  12. 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

    Article  Google Scholar 

  13. 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

    Article  MATH  Google Scholar 

  14. 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

    Article  MATH  MathSciNet  Google Scholar 

  15. 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

    Google Scholar 

  16. Cheng TCE, Chen ZL (1994) Parallel-machine scheduling with earliness and tardiness penalties. J Oper Res Soc 45:685–695

    Article  MATH  Google Scholar 

  17. Dorigo M, Stuetzle T (2004) Ant colony optimization. MIT, Boston, MA

    MATH  Google Scholar 

  18. 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

    Article  MATH  MathSciNet  Google Scholar 

  19. 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

    Article  MATH  MathSciNet  Google Scholar 

  20. 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

    Article  MATH  Google Scholar 

  21. 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

  22. 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

    Google Scholar 

  23. 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

    Article  Google Scholar 

  24. 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

    Article  MATH  MathSciNet  Google Scholar 

  25. 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

    Article  MathSciNet  Google Scholar 

  26. 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

    Article  MATH  MathSciNet  Google Scholar 

  27. 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

    Article  MATH  Google Scholar 

  28. 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

    Article  MATH  Google Scholar 

  29. 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

    Article  MATH  MathSciNet  Google Scholar 

  30. Hoogeveen JA (2005) Multicriteria scheduling. Eur J Oper Res 167:592–623. doi:10.1016/j.ejor.2004.07.011

    Article  MATH  MathSciNet  Google Scholar 

  31. 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

    Article  Google Scholar 

  32. 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

    Article  Google Scholar 

  33. 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

    Article  Google Scholar 

  34. Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680. doi:10.1126/science.220.4598.671

    Article  MathSciNet  Google Scholar 

  35. 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

    Article  MathSciNet  Google Scholar 

  36. 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

    Article  MATH  Google Scholar 

  37. 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

    Article  MATH  Google Scholar 

  38. Lam K, Xing W (1997) New trends in parallel machine scheduling. Int J Oper Manage 17:326–338. doi:10.1108/01443579710159932

    Article  Google Scholar 

  39. 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

    Article  MATH  MathSciNet  Google Scholar 

  40. 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

    Article  MATH  Google Scholar 

  41. 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

    Article  MathSciNet  Google Scholar 

  42. 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

    Article  Google Scholar 

  43. Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097–1100. doi:10.1016/S0305-0548(97)00031-2

    Article  MATH  MathSciNet  Google Scholar 

  44. Montgomery DC (2000) Design and analysis of experiments, 5th edn. Wiley, New York

    Google Scholar 

  45. 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

  46. 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

    Article  Google Scholar 

  47. Pinedo M (1995) Scheduling theory, algorithms, and systems. Prentice-Hall, Englewood Cliffs, NJ

    MATH  Google Scholar 

  48. 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

    Article  MATH  Google Scholar 

  49. 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

    Article  MATH  Google Scholar 

  50. 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

    Article  MATH  Google Scholar 

  51. 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

    Article  MATH  MathSciNet  Google Scholar 

  52. 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

    Google Scholar 

  53. 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

    Article  Google Scholar 

  54. Talbi E (2002) A taxonomy of hybrid metaheuristics. J Heuristics 8(5):541–564. doi:10.1023/A:1016540724870

    Article  Google Scholar 

  55. 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

  56. 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

    Article  MATH  Google Scholar 

  57. 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

    Article  MATH  Google Scholar 

  58. 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

  59. 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

    Article  MATH  MathSciNet  Google Scholar 

  60. Yao X (1995) A new simulated annealing algorithm. Int J Comput Math 56:161–168. doi:10.1080/00207169508804397

    Article  MATH  Google Scholar 

  61. 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

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, Amirkabir University of Technology, 424 Hafez Avenue, Tehran, Iran

    J. Behnamian & S. M. T. Fatemi Ghomi

  2. Department of Industrial Management, Management and Accounting Faculty, Shahid Beheshti University, Tehran, Iran

    M. Zandieh

Authors
  1. J. Behnamian
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Zandieh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. M. T. Fatemi Ghomi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Zandieh.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-008-1885-7

Keywords

Search

Navigation