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

Population-based iterated local search for batch scheduling on parallel machines with incompatible job families, release dates, and tardiness penalties

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This work addresses a parallel batch machine scheduling problem subject to tardiness penalties, release dates, and incompatible job families. In this environment, jobs of the same family are partitioned into batches and each batch is assigned to a machine. The objective is to determine the sequence in which the batches will be processed on each machine with a view of minimizing the total weighted tardiness. To solve the problem, we propose a population-based iterated local search algorithm that makes use of multiple neighborhood structures and an efficient perturbation mechanism. The algorithm also incorporates the time window decomposition (TWD) heuristic to generate the initial population and employs population control strategies aiming to promote individuals with higher fitness by combining the total weighted tardiness with the contribution to the diversity of the population. Extensive computational experiments were conducted on 4860 benchmark instances and the results obtained compare very favorably with those found by the best existing algorithms.

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

Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Fig. 1

Similar content being viewed by others

Data availability

The datasets analyzed during the current study are available from the corresponding author on reasonable request.

References

  1. Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979). https://doi.org/10.1016/S0167-5060(08)70356-X

    Article  MathSciNet  MATH  Google Scholar 

  2. Lawler, E.L.: A “pseudopolynomial’’ algorithm for sequencing jobs to minimize total tardiness. Ann. Discrete Math. 1, 331–342 (1977). https://doi.org/10.1016/S0167-5060(08)70742-8

    Article  MathSciNet  MATH  Google Scholar 

  3. Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Sterna, M., Weglarz, J.: Handbook on Scheduling: From Theory to Practice. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-99849-7

    Book  MATH  Google Scholar 

  4. Fowler, J.W., Möh, L.: A survey of scheduling with parallel batch (p-batch) processing. Eur. J. Oper. Res. 298, 1–24 (2022). https://doi.org/10.1016/j.ejor.2021.06.012

    Article  MathSciNet  MATH  Google Scholar 

  5. Vimala Rani, M., Mathirajan, M.: A state-of-art review and a simple meta-analysis on deterministic scheduling of diffusion furnaces in semiconductor manufactoring. Int. J. Prod. Res. 61(16), 5744–5771 (2022). https://doi.org/10.1080/00207543.2022.2102449

    Article  MATH  Google Scholar 

  6. Lee, C.-Y., Uzsoy, R., Martin-Vega, L.A.: Efficient algorithms for scheduling semiconductor burn-in operations. Oper. Res. 40(4), 764–775 (1992). https://doi.org/10.1287/opre.40.4.764

    Article  MathSciNet  MATH  Google Scholar 

  7. Mönch, L., Balasubramanian, H., Fowler, J.W., Pfund, M.E.: Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Comput. Oper. Res. 32(11), 2731–2750 (2005). https://doi.org/10.1016/j.cor.2004.04.001

    Article  MATH  Google Scholar 

  8. Chiang, T.-C., Cheng, H.-C., Fu, L.-C.: A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival. Comput. Oper. Res. 37(12), 2257–2269 (2010). https://doi.org/10.1016/j.cor.2010.03.017

    Article  MathSciNet  MATH  Google Scholar 

  9. Bilyk, A., Mönch, L., Almeder, C.: Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics. Comput. Ind. Eng. 78, 175–185 (2014). https://doi.org/10.1016/j.cie.2014.10.008

    Article  MATH  Google Scholar 

  10. Fidelis, M.B., Arroyo, J.E.C.: Meta-heuristic algorithms for scheduling on parallel batch machines with unequal job ready times. In: 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 542–547. IEEE, Banff (2017). https://doi.org/10.1109/SMC.2017.8122662

  11. Klemmt, A., Weigert, G., Almeder, C., Monch, L.: A comparison of MIP-based decomposition techniques and VNS approaches for batch scheduling problems. In: Proceedings of the 2009 Winter Simulation Conference (WSC), pp. 1686–1694. IEEE (2009)

  12. Eray Cakici, J.W.F., Mason, Scott J., Geismar, H.N.: Batch scheduling on parallel machines with dynamic job arrivals and incompatible job families. Int. J. Prod. Res. 51(8), 2462–2477 (2013). https://doi.org/10.1080/00207543.2012.748227

    Article  MATH  Google Scholar 

  13. Ham, A., Fowler, J.W., Cakici, E.: Constraint programming approach for scheduling jobs with release times, non-identical sizes, and incompatible families on parallel batching machines. IEEE Trans. Semicond. Manuf. 30(4), 500–507 (2017). https://doi.org/10.1109/TSM.2017.2740340

    Article  MATH  Google Scholar 

  14. Lackner, M.-L., Mrkvicka, C., Musliu, N., Walkiewicz, D., Winter, F.: Exact methods for the oven scheduling problem. Constraints 28(2), 320–361 (2023). https://doi.org/10.1007/s10601-023-09347-2

    Article  MathSciNet  MATH  Google Scholar 

  15. Vepsalainen, A.P.J., Morton, T.E.: Priority rules for job shops with weighted tardiness costs. Manag. Sci. 33(8), 1035–1047 (1987). https://doi.org/10.1287/mnsc.33.8.1035

    Article  MATH  Google Scholar 

  16. Subramanian, A., Drummond, LMd.A., Bentes, C., Ochi, L.S., Farias, R.: A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Comput. Oper. Res. 37(11), 1899–1911 (2010). https://doi.org/10.1016/j.cor.2009.10.011

    Article  MATH  Google Scholar 

  17. Queiroga, E., Pinheiro, R.G.S., Christ, Q., Subramanian, A., Pessoa, A.A.: Iterated local search for single machine total weighted tardiness batch scheduling. J. Heuristics 27, 353–438 (2021). https://doi.org/10.1007/s10732-020-09461-x

    Article  MATH  Google Scholar 

  18. Vidal, T., Crainic, T.G., Gendreau, M., Lahrichi, N., Rei, W.: A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60, 611–624 (2012). https://doi.org/10.1287/opre.1120.1048

    Article  MathSciNet  MATH  Google Scholar 

  19. Lubin, M., Dowson, O., Dias Garcia, J., Huchette, J., Legat, B., Vielma, J.P.: JuMP 1.0: recent improvements to a modeling language for mathematical optimization. Math. Program. Comput. (2023). https://doi.org/10.1007/s12532-023-00239-3

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This research was partially supported by the Brazilian research agencies CNPq, Grants 406245/2021-5, 309580/2021-8 and 150881/2023-1, and Paraíba State Research Foundation (FAPESQ), Grants 2021/3182 and 2390/2023, as well as by Universidade Federal da Paraíba through the Public Call N. 03/2020 “Produtividade em Pesquisa PROPESQ/PRPG/UFPB”, proposal codes PVL13395-202 and PVL13400-2020.

Author information

Authors and Affiliations

  1. Programa de Pós-Graduação em Informática, Centro de Informática, Universidade Federal da Paraíba, João Pessoa, PB, 58058-600, Brazil

    José Maurício Fernandes Medeiros & Eduardo Queiroga

  2. Departamento de Sistemas de Computação, Centro de Informática, Universidade Federal da Paraíba, João Pessoa, PB, 58058-600, Brazil

    Anand Subramanian

Authors
  1. José Maurício Fernandes Medeiros
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anand Subramanian
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eduardo Queiroga
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to José Maurício Fernandes Medeiros.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Medeiros, J.M.F., Subramanian, A. & Queiroga, E. Population-based iterated local search for batch scheduling on parallel machines with incompatible job families, release dates, and tardiness penalties. Optim Lett 19, 193–210 (2025). https://doi.org/10.1007/s11590-024-02116-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-024-02116-x

Keywords