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

Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

In this paper we investigate the problem of scheduling a set of jobs on a single-machine. The jobs are classified in families and setup times are required between the processing of two jobs of different families. Each job requires a certain amount of a common resource that is supplied through upstream processes. The total resource consumed must not exceed the resource supply up. Therefore, jobs may have to wait and the machine has to be idle due to an insufficient availability of the resource. To minimize the total tardiness, simple and effective iterated greedy (IG) heuristics are proposed. Different neighborhood operators are used in the local search phase. To choose the right neighborhood operators, we propose an adaptive selecting strategy. The heuristics are tested over an extensive computational experience on benchmark of instances from the literature and instances randomly generated in this work. Experimental results and statistical tests show that the proposed heuristics are able to obtain high-quality solutions within reasonable computational effort, and they outperform the state-of-the-art heuristic.

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

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Herr, O., Goel, A.: Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints. Eur. J. Oper. Res. 248(1), 123–135 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  2. Du, J., Leung, J.Y.-T.: Minimizing total tardiness on one machine is np-hard. Math. Oper. Res. 15(3), 483–495 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  3. Koulamas, C.: The single-machine total tardiness scheduling problem: review and extensions. Eur. J. Oper. Res. 202(1), 1–7 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Sen, T., Sulek, J.M., Dileepan, P.: Static scheduling research to minimize weighted and unweighted tardiness: a state-of-the-art survey. Int. J. Prod. Econ. 83(1), 1–12 (2003)

    Article  Google Scholar 

  5. Emmons, H.: One-machine sequencing to minimize certain functions of job tardiness. Oper. Res. 17(4), 701–715 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  6. Lawler, E.L.: A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Ann. Discrete Math. 1, 331–342 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  7. Allahverdi, A., Ng, C., Cheng, T.E., Kovalyov, M.Y.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187(3), 985–1032 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Potts, C.N., Kovalyov, M.Y.: Scheduling with batching: a review. Eur. J. Oper. Res. 120(2), 228–249 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gupta, S.R., Smith, J.S.: Algorithms for single machine total tardiness scheduling with sequence dependent setups. Eur. J. Oper. Res. 175(2), 722–739 (2006)

    Article  MATH  Google Scholar 

  10. Liao, C.-J., Juan, H.-C.: An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Comput. Oper. Res. 34(7), 1899–1909 (2007)

    Article  MATH  Google Scholar 

  11. Lin, S., Ying, K.: A hybrid approach for single-machine tardiness problems with sequence-dependent setup times. J. Oper. Res. Soc. 59(8), 1109–1119 (2008)

    Article  Google Scholar 

  12. 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. Appl. 36(3), 7087–7092 (2009)

    Article  Google Scholar 

  13. Sioud, A., Gravel, M., Gagné, C.: A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times. Comput. Oper. Res. 39(10), 2415–2424 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bigras, L.-P., Gamache, M., Savard, G.: The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Discret. Optim. 5(4), 685–699 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. Tanaka, S., Araki, M.: An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Comput. Oper. Res. 40(1), 344–352 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  16. Subramanian, A., Battarra, M., Potts, C.N.: An iterated local search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. Int. J. Prod. Res. 52(9), 2729–2742 (2014)

    Article  Google Scholar 

  17. Gupta, J.N., Chantaravarapan, S.: Single machine group scheduling with family setups to minimize total tardiness. Int. J. Prod. Res. 46(6), 1707–1722 (2008)

    Article  MATH  Google Scholar 

  18. Schaller, J.: Scheduling on a single machine with family setups to minimize total tardiness. Int. J. Prod. Econ. 105(2), 329–344 (2007)

    Article  Google Scholar 

  19. Potts, C.N., Van Wassenhove, L.N.: Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity. J. Oper. Res. Soc. 43(5), 395–406 (1992)

    Article  MATH  Google Scholar 

  20. Schaller, J.E., Gupta, J.N.: Single machine scheduling with family setups to minimize total earliness and tardiness. Eur. J. Oper. Res. 187(3), 1050–1068 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  21. Vilar Jacob, V., Arroyo, J.E.C.: Ils heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness. J. Appl. Math. 2016 (2016)

  22. Peng, Y., Han, Y., Xiao, Y., Ullah, S.: Heuristics for single machine scheduling problem with family setup times. Int. J. Comput. Sci. Math. 8(2), 166–174 (2017)

    Article  MathSciNet  Google Scholar 

  23. Briskorn, D., Choi, B.-C., Lee, K., Leung, J., Pinedo, M.: Complexity of single machine scheduling subject to nonnegative inventory constraints. Eur. J. Oper. Res. 207(2), 605–619 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  24. Briskorn, D., Jaehn, F., Pesch, E.: Exact algorithms for inventory constrained scheduling on a single machine. J. Sched. 16(1), 105–115 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  25. Fanjul-Peyro, L., Ruiz, R.: Iterated greedy local search methods for unrelated parallel machine scheduling. Eur. J. Oper. Res. 207(1), 55–69 (2010)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  27. Ruiz, R., Pan, Q.-K., Naderi, B.: Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega (2018)

  28. Rodriguez, F.J., Lozano, M., Blum, C., García-Martínez, C.: An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Comput. Oper. Res. 40(7), 1829–1841 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  29. Kang, Q., He, H., Wei, J.: An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems. J. Parallel Distrib. Comput. 73(8), 1106–1115 (2013)

    Article  Google Scholar 

  30. Zhou, S., Liu, M., Chen, H., Li, X.: An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes. Int. J. Prod. Econ. 179, 1–11 (2016)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Universidade Federal de Viçosa, Viçosa, MG, 36570-900, Brazil

    Júlio C. S. N. Pinheiro & José Elias C. Arroyo

Authors
  1. Júlio C. S. N. Pinheiro
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José Elias C. Arroyo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to José Elias C. Arroyo.

Additional information

Publisher’s note

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

The authors thanks the financial support of CNPq and FAPEMIG, brazilian research agencies.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pinheiro, J.C.S.N., Arroyo, J.E.C. Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints. Ann Math Artif Intell 88, 169–185 (2020). https://doi.org/10.1007/s10472-019-09646-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10472-019-09646-6

Keywords

Mathematics Subject Classification (2010)

Search

Navigation