Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Variable neighborhood search for the single machine scheduling problem to minimize the total early work

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

Abstract

In this paper, the single machine scheduling problem to minimize the total early work is studied. The aim of this problem is to minimize the total amount of processing performed on the jobs before their due dates. We have proposed a better implementation of the existing dynamic programming method and thus solved large problems in an exact way. In particular, we can currently resolve instances of sizes 10,000 exactly instead of 200 with a pseudo-polynomial dynamic programming algorithm. Since the considered problem was proven to be NP-hard, a heuristic based on the Variable Neighborhood Search (VNS) method is proposed to solve larger instances. Computational experiments show that both methods are efficient.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Alhadi, G., Kacem, I., Laroche, P., Osman, I.M.: Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines. Ann. Oper. Res. 285(1), 369–395 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  2. Almiñana, M., Escudero, L., Landete, M., Monge, J., Rabasa, A., Sánchez-Soriano, J.: Wische: A dss for water irrigation scheduling. Omega 38(6), 492–500 (2010)

    Article  Google Scholar 

  3. Ben-Yehoshua, Y., Mosheiov, G.: A single machine scheduling problem to minimize total early work. Comput. Oper. Res. 73, 115–118 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  4. Benmansour, R., Allaoui, H., Artiba, A., Hanafi, S.: Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance. Comput. Oper. Res. 47, 106–113 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  5. Blazewicz, J.: Scheduling preemptible tasks on parallel processors with information with loss. Parallel Comput. 26(2000), 1195–1211 (1984)

    MATH  Google Scholar 

  6. Błaewicz, J., Ecker, KH., Pesch, E., Schmidt, G., Weglarz, J.: (2007) Handbook on scheduling: from theory to applications. Springer Science & Business Media

  7. Chen, X., Kovalev, S., Sterna, M., Blazewicz, J.: Mirror scheduling problems with early work and late work criteria. J. Scheduling 24, 483–487 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  8. Garey, M.R., Johnson, D.S.: Computers and intractability, vol. 174. Freeman, San Francisco (1979)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  10. Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. Eur. J. Operat. Res. 130(3), 449–467 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hansen, P., Mladenović, N., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optimiz. 5(3), 423–454 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  12. Hochbaum, D.S., Shamir, R.: Minimizing the number of tardy job units under release time constraints. Discrete Appl. Math. 28(1), 45–57 (1990)

    Article  MATH  Google Scholar 

  13. Khalouli, S., Benmansour, R., Hanafi, S.: An ant colony algorithm based on opportunities for scheduling the preventive railway maintenance. In: 2016 International Conference on Control, pp. 594–599. Decision and Information Technologies (CoDIT), IEEE (2016)

  14. Khalouli, S., Benmansour, R., Hanafi, S.: Ant colony optimisation combined with variable neighbourhood search for scheduling preventive railway maintenance activities. Int. J. Intell. Eng. Info. 6(1–2), 78–98 (2018)

    Google Scholar 

  15. Krimi, I., Todosijević, R., Benmansour, R., Ratli, M., El Cadi, A.A., Aloullal, A.: Modelling and solving the multi-quays berth allocation and crane assignment problem with availability constraints. J. Global Optimiz. 78(2), 349–373 (2020)

    Article  MathSciNet  Google Scholar 

  16. Menéndez, B., Bustillo, M., Pardo, E.G., Duarte, A.: General variable neighborhood search for the order batching and sequencing problem. Eur. J. Operat. Res. 263(1), 82–93 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  17. Mikić, M., Todosijević, R., Urošević, D.: Less is more: general variable neighborhood search for the capacitated modular hub location problem. Comput. Oper. Res. 110, 101–115 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  18. Mjirda, A., Todosijević, R., Hanafi, S., Hansen, P., Mladenović, N.: Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem. Int. Trans. Oper. Res. 24(3), 615–633 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  19. Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  20. M’Hallah, R., Alhajraf, A.: Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem. J. Scheduling 19(2), 191–205 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  21. Potts, C.N., Van Wassenhove, L.N.: Single machine scheduling to minimize total late work. Oper. Res. 40(3), 586–595 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  22. Ren, J., Zhang, Y., Sun, G.: The np-hardness of minimizing the total late work on an unbounded batch machine. Asia-Pacific J. Oper. Res. 26(03), 351–363 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  23. Sánchez-Oro, J., Mladenović, N., Duarte, A.: General variable neighborhood search for computing graph separators. Optimiz. Lett. 11(6), 1069–1089 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  24. Sterna, M.: A survey of scheduling problems with late work criteria. Omega 39(2), 120–129 (2011)

    Article  Google Scholar 

  25. Sterna, M.: (2021) Late and early work scheduling: a survey. Omega p 102453

  26. Todosijević, R., Benmansour, R., Hanafi, S., Mladenović, N., Artiba, A.: Nested general variable neighborhood search for the periodic maintenance problem. Eur. J. Oper. Res. 252(2), 385–396 (2016)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut National de Statistiques et d’Economie Appliquée (INSEA), Rabat, Morocco

    Rachid Benmansour

  2. LAMIH UMR CNRS 8201, Université Polytechnique Hauts de France, Valenciennes, France

    Rachid Benmansour, Raca Todosijević & Saïd Hanafi

Authors
  1. Rachid Benmansour
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raca Todosijević
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Saïd Hanafi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rachid Benmansour.

Additional information

Publisher's Note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Benmansour, R., Todosijević, R. & Hanafi, S. Variable neighborhood search for the single machine scheduling problem to minimize the total early work. Optim Lett 17, 2169–2184 (2023). https://doi.org/10.1007/s11590-022-01913-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-022-01913-6

Keywords

Search

Navigation