[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Effective Heuristics and an Iterated Greedy Algorithm to Schedule Identical Parallel Machines Subject to Common Restrictive Due Windows

  • Research Article-Systems Engineering
  • Published:
Arabian Journal for Science and Engineering Aims and scope Submit manuscript

Abstract

In this paper, we address a variant of the identical parallel machines scheduling problem subject to common restrictive due windows. The performance measure adopted is the minimization of total weighted earliness and tardiness. Since the variant under study is an NP-hard problem for two or more machines, we develop a family of constructive heuristics, which are comprised of four phases. First, jobs are sequenced according to priority rules. Second, jobs are assigned to machines using a greedy strategy. Third, a local search is performed to find a better distribution of jobs into machines. Fourth, two heuristics are applied for individually sequencing jobs in each machine, namely RN-RGH and RN-SEA. In addition, we also propose an iterated greedy algorithm to improve the solutions of the best performing heuristic. The computational experiments were carried out to prove the ability of these heuristics to find high-quality solutions in acceptable CPU time. More specifically, the RN-SEA family of algorithms stands out as the most efficient for the problem, however, with a higher computational effort. We also confirm that the IG algorithm has the potential for improving existing solutions, specially for problems with two machines and instances with up to 100 jobs in size.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Data Availability and Material

The test instances have been presented previously by Biskup and Feldmann [34]. All the evaluated test instances are available in this link: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/schinfo.html.

Notes

  1. http://people.brunel.ac.uk/~mastjjb/jeb/info.html.

References

  1. Baker, K.R.; Scudder, G.D.: Sequencing with earliness and tardiness penalties: a review. Oper. Res. 38(1), 22–36 (1990). https://doi.org/10.1287/opre.38.1.22

    Article  MathSciNet  MATH  Google Scholar 

  2. Choi, B.C.; Park, M.J.: Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty. J. Comb. Optim. 41, 781–793 (2021)

    Article  MathSciNet  Google Scholar 

  3. Gordon, V.S.; Proth, J.M.; Chu, C.: Due date assignment and scheduling: SLK, TWK and other due date assignment models. Prod. Plann. Control 13(2), 117–132 (2002). https://doi.org/10.1080/09537280110069621

    Article  Google Scholar 

  4. Mor, B.; Mosheiov, G.: A note on the single machine CON and CONW problems with lot scheduling. J. Combinat. Optim. 42, 327–38 (2021)

    Article  MathSciNet  Google Scholar 

  5. Rolim, G.A.; Nagano, M.S.: Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review. Comput. Ind. Eng. (2020). https://doi.org/10.1016/j.cie.2020.106803

    Article  Google Scholar 

  6. Biskup, D.; Feldmann, M.: On scheduling around large restrictive common due windows. Eur. J. Oper. Res. 162(3), 740–761 (2005). https://doi.org/10.1016/j.ejor.2003.10.026

    Article  MathSciNet  MATH  Google Scholar 

  7. Janiak, A.; Janiak, W.A.; Krysiak, T.; Kwiatkowski, T.: A survey on scheduling problems with due windows. Eur. J. Oper. Res. 242(2), 347–357 (2015). https://doi.org/10.1016/j.ejor.2014.09.043

    Article  MathSciNet  MATH  Google Scholar 

  8. Koulamas, C.: Single-machine scheduling with time windows and earliness/tardiness penalties. Eur. J. Oper. Res. 91(1), 190–202 (1996). https://doi.org/10.1016/0377-2217(95)00116-6

    Article  MathSciNet  MATH  Google Scholar 

  9. Wu, Y.; Lai, K.K.: A production scheduling strategy with a common due window. Comput. Ind. Eng. 53(2), 215–221 (2007). https://doi.org/10.1016/j.cie.2007.06.012

    Article  Google Scholar 

  10. Mönch, L.; Unbehaun, R.; Choung, Y.I.: Minimizing earliness-tardiness on a single burn-in oven with a common due date and maximum allowable tardiness constraint. OR Spectrum 28(2), 177–198 (2006). https://doi.org/10.1007/s00291-005-0013-4

    Article  MathSciNet  MATH  Google Scholar 

  11. Mönch, L.; Fowler, J.W.; Dauzère-Pérès, S.; Mason, S.J.; Rose, O.: A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. J. Sched. 14(6), 583–599 (2011). https://doi.org/10.1007/s10951-010-0222-9

    Article  MathSciNet  Google Scholar 

  12. Rocholl, J.; Mönch, L.: Hybrid algorithms for the earliness-tardiness single-machine multiple orders per job scheduling problem with a common due date. RAIRO-Oper. Rese. 52(4–5), 1329–1350 (2018). https://doi.org/10.1051/ro/2018029

    Article  MathSciNet  MATH  Google Scholar 

  13. Mula, J.; Bogataj, M.: OR in the industrial engineering of industry 4.0: experiences from the iberian peninsula mirrored in CJOR. Central Eur. J. Oper. Res. (2021). https://doi.org/10.1007/s10100-021-00740-x

    Article  MATH  Google Scholar 

  14. Chen, Z.L.; Lee, C.Y.: Parallel machine scheduling with a common due window. Eur. J. Oper. Res. 136(3), 512–527 (2002). https://doi.org/10.1016/s0377-2217(01)00068-6

    Article  MathSciNet  MATH  Google Scholar 

  15. Kramer, F.J.; Lee, C.Y.: Due window scheduling for parallel machines. Math. Comput. Modell. 20(2), 69–89 (1994). https://doi.org/10.1016/0895-7177(94)90208-9

    Article  MathSciNet  MATH  Google Scholar 

  16. Mosheiov, G.; Oron, D.: Due-window assignment with unit processing-time jobs. Naval Res. Logist. 51(7), 1005–1017 (2004). https://doi.org/10.1002/nav.20039

    Article  MathSciNet  MATH  Google Scholar 

  17. Mosheiov, G.; Sarig, A.: A note: a due-window assignment problem on parallel identical machines. J. Oper. Res. Soc. 62(1), 238–241 (2011). https://doi.org/10.1057/jors.2009.179

    Article  Google Scholar 

  18. Janiak, A.; Janiak, W.; Kovalyov, M.Y.; Werner, F.: Soft due window assignment and scheduling of unit-time jobs on parallel machines. 4OR Quart. J. Oper. Res. 10(4), 347–360 (2012). https://doi.org/10.1007/s10288-012-0201-4

    Article  MathSciNet  MATH  Google Scholar 

  19. Gerstl, E.; Mosheiov, G.: An improved algorithm for due-window assignment on parallel identical machines with unit-time jobs. Inf. Process. Lett. 113(19–21), 754–759 (2013b). https://doi.org/10.1016/j.ipl.2013.06.013

    Article  MathSciNet  MATH  Google Scholar 

  20. Mosheiov, G.; Sarig, A.: Scheduling identical jobs and due-window on uniform machines. Eur. J. Oper. Res. 201(3), 712–719 (2010). https://doi.org/10.1016/j.ejor.2009.03.039

    Article  MathSciNet  MATH  Google Scholar 

  21. Gerstl, E.; Mosheiov, G.: Due-window assignment with identical jobs on parallel uniform machines. Eur. J. Oper. Res. 229(1), 41–47 (2013a). https://doi.org/10.1016/j.ejor.2012.12.034

    Article  MathSciNet  MATH  Google Scholar 

  22. Janiak, A.; Janiak, W.; Kovalyov, M.Y.; Kozan, E.; Pesch, E.: Parallel machine scheduling and common due window assignment with job independent earliness and tardiness costs. Inf. Sci. 224, 109–117 (2013). https://doi.org/10.1016/j.ins.2012.10.024

    Article  MathSciNet  MATH  Google Scholar 

  23. Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discr. Math. 5, 287–326 (1979)

    Article  MathSciNet  Google Scholar 

  24. Alvarez-Valdes, R.; Tamarit, J.M.; Villa, F.: Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics. Comput. Oper. Res. 54, 1–11 (2015). https://doi.org/10.1016/j.cor.2014.08.020

    Article  MathSciNet  MATH  Google Scholar 

  25. Ying, K.C.; Lin, S.W.; Lu, C.C.: Effective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window. Int. J. Prod. Res. 55(6), 1707–1719 (2017). https://doi.org/10.1080/00207543.2016.1224949

    Article  Google Scholar 

  26. Lin, S.W.; Chou, S.Y.; Ying, K.C.: A sequential exchange approach for minimizing earliness-tardiness penalties of single-machine scheduling with a common due date. Eur. J. Oper. Res. 177(2), 1294–1301 (2007). https://doi.org/10.1016/j.ejor.2005.11.015

    Article  MATH  Google Scholar 

  27. Ruiz, R.; Stützle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur. J. Oper. Res. 177(3), 2033–2049 (2007). https://doi.org/10.1016/j.ejor.2005.12.009

    Article  MATH  Google Scholar 

  28. Arroyo, J.E.C.; Leung, J.Y.T.: An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times. Comput. Ind. Eng. 105, 84–100 (2017). https://doi.org/10.1016/j.cie.2016.12.038

    Article  Google Scholar 

  29. Ribas, I.; Companys, R.; Tort-Martorell, X.: An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem. Expert Syst. Applic. 121, 347–361 (2019). https://doi.org/10.1016/j.eswa.2018.12.039

    Article  Google Scholar 

  30. Lin, S.W.; Lu, C.C.; Ying, K.C.: 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(1–4), 353–361 (2011b). https://doi.org/10.1007/s00170-010-2824-y

    Article  Google Scholar 

  31. Ying, K.C.; Lin, S.W.; Huang, C.Y.: Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Syst. Applic. 36(3), 7087–7092 (2009). https://doi.org/10.1016/j.eswa.2008.08.033

    Article  Google Scholar 

  32. Kang, Q.; He, H.; Wei, J.: An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems. J. Parall. Distrib. Comput. 73(8), 1106–1115 (2013). https://doi.org/10.1016/j.jpdc.2013.03.008

    Article  Google Scholar 

  33. Lin, S.W.; Lee, Z.J.; Ying, K.C.; Lu, C.C.: Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates. Comput. Operat. Res. 38(5), 809–815 (2011a). https://doi.org/10.1016/j.cor.2010.09.020

    Article  MathSciNet  MATH  Google Scholar 

  34. Biskup, D.; Feldmann, M.: Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Comput. Oper. Res. 28(8), 787–801 (2001). https://doi.org/10.1016/s0305-0548(00)00008-3

    Article  MATH  Google Scholar 

  35. Beasley, J.E.: OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990). https://doi.org/10.1057/jors.1990.166

    Article  Google Scholar 

  36. Chen, Z.L.; Powell, W.B.: A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. Eur. J. Oper. Res. 116(1), 220–232 (1999). https://doi.org/10.1016/s0377-2217(98)00136-2

    Article  MATH  Google Scholar 

Download references

Funding

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001. This work was partially funded by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) through Grants 404232/2016-7, 306075/2017-2, 430137/2018-4, 130396/2018-4, and 303594/2018-7.

Author information

Authors and Affiliations

  1. Department of Production Engineering, São Carlos School of Engineering, University of São Paulo, São Carlos, Brazil

    Gustavo Alencar Rolim & Marcelo Seido Nagano

  2. Department of Industrial Engineering, Federal University of Ceará, Campus do Pici, Fortaleza, Brazil

    Bruno de Athayde Prata

Authors
  1. Gustavo Alencar Rolim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcelo Seido Nagano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bruno de Athayde Prata
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

GAR helped in investigation, software, formal analysis, writing—original draft, visualization; MSN contributed to conceptualization, writing—original draft, writing—review and editing, supervision, project administration, funding acquisition; BAP helped in writing—original draft, writing—review and editing, supervision, funding acquisition.

Corresponding author

Correspondence to Marcelo Seido Nagano.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Rolim, G.A., Nagano, M.S. & Prata, B.d.A. Effective Heuristics and an Iterated Greedy Algorithm to Schedule Identical Parallel Machines Subject to Common Restrictive Due Windows. Arab J Sci Eng 47, 3899–3913 (2022). https://doi.org/10.1007/s13369-021-06244-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13369-021-06244-9

Keywords