SpringerLink
Log in

Single-machine due-date assignment scheduling with generalized earliness-tardiness penalties including proportional setup times

  • Original Research
  • Published:
Journal of Applied Mathematics and Computing Aims and scope Submit manuscript

Abstract

This paper studies the single-machine due-date assignment problem with past-sequence-dependent setup times (denoted by \(ST_{psd}\)). Under common due-date (denoted by CON-DD) assignment, slack due-date (denoted by SLK-DD) and different due-date (denoted by DIF-DD) assignment, the objective function is to minimize the linear weighted sum of earliness-tardiness, number of early and delayed jobs, and due-date cost. Optimal properties of the problem is given and then prove that the problem can be solved in polynomial time. Three extensions to the problem are also offered by assuming position-dependent, time-dependent, position-and-time-dependent processing times.

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

Similar content being viewed by others

References

  1. Adamopoulos, G.I., Pappis, C.P.: Single machine scheduling with flow allowances. J. Oper. Res. Soc. 47, 1280–1285 (1996)

    Article  Google Scholar 

  2. Allahverdi, A.: The third comprehensive survey on scheduling problems with setup times/costs. Eur. J. Oper. Res. 246, 345–378 (2015)

    Article  MathSciNet  Google Scholar 

  3. Azzouz, A., Ennigrou, M., Said, L.B.: Scheduling problems under learning effects: classification and cartography. Int. J. Prod. Res. 56(4), 1642–1661 (2018)

    Article  Google Scholar 

  4. Birgin, E.G., Ronconi, D.P.: Heuristic methods for the single machine scheduling problem with different ready times and a common due date. Eng. Optim. 44(10), 1197–1208 (2012)

    Article  MathSciNet  Google Scholar 

  5. Biskup, D.: Single-machine scheduling with learning considerations. Eur. J. Oper. Res. 115(1), 173–178 (1999)

    Article  Google Scholar 

  6. Biskup, D.: A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res. 188, 315–329 (2008)

    Article  MathSciNet  Google Scholar 

  7. Biskup, D., Herrmann, J.: Single-machine scheduling against due dates with past-sequence-dependent setup times. Eur. J. Oper. Res. 191, 587–592 (2008)

    Article  MathSciNet  Google Scholar 

  8. Cheng, T.C.E., Lee, W.-C., Wu, C.-C.: Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Comput. Ind. Eng. 58, 326–331 (2010)

    Article  Google Scholar 

  9. Cheng, T.C.E., Lee, W.-C., Wu, C.-C.: Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times. Appl. Math. Model. 35, 1861–1867 (2011)

    Article  MathSciNet  Google Scholar 

  10. Gawiejnowicz, S.: Models and Algorithms of Time-Dependent Scheduling. Springer, Berlin (2020)

    Book  Google Scholar 

  11. Gordon, V.S., Proth, J.M., Chu, C.B.: A survey of the state of-the-art of common due date assignment and scheduling research. Eur. J. Oper. Res. 139, 1–25 (2002)

    Article  MathSciNet  Google Scholar 

  12. Gordon, V.S., Proth, J.M., Chu, C.B.: Due date assignment and scheduling: SLK, TWK and other due date assignment models. Prod. Plan. Control 13, 117–132 (2002)

    Article  Google Scholar 

  13. Hardy, G.H., Littlewood, J.E., Polya, G.: Inequalities, 2nd edn. Cambridge University Press, Cambridge, UK (1967)

    MATH  Google Scholar 

  14. Hsu, C.-J., Kuo, W.-H., Yang, D.-L.: Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects. Appl. Math. Model. 35, 1492–1496 (2011)

    Article  MathSciNet  Google Scholar 

  15. Huang, X., Li, G., Huo, Y., Ji, P.: Single machine scheduling with general time-dependent deterioration, position-dependent learning and past sequence-dependent setup times. Optim. Lett. 7, 1793–1804 (2013)

    Article  MathSciNet  Google Scholar 

  16. Koulamas, C.: Common due date assignment with generalized earliness/tardiness penalties. Comput. Ind. Eng. 109, 79–83 (2017)

    Article  Google Scholar 

  17. Koulamas, C., Kyparisis, G.J.: Single-machine scheduling problems with past-sequence-dependent setup times. Eur. J. Oper. Res. 187, 1045–1049 (2008)

    Article  MathSciNet  Google Scholar 

  18. Koulamas, C., Kyparisis, G.J.: New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives. Eur. J. Oper. Res. 278, 149–159 (2019)

    Article  MathSciNet  Google Scholar 

  19. Kuo, W.-H., Hsu, C.-J., Yang, D.-L.: Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects. Comput. Ind. Eng. 61, 179–183 (2011)

    Article  Google Scholar 

  20. Liang, X.-X., Zhang, B., Wang, J.-B., Yin, N., Huang, X.: Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects. J. Appl. Math. Comput. 61, 373–388 (2019)

    Article  MathSciNet  Google Scholar 

  21. Lu, Y.-Y., Li, G., Wu, Y.-B., Ji, P.: Optimal due-date assignment problem with learning effect and resource-dependent processing times. Optim. Lett. 8, 113–127 (2014)

    Article  MathSciNet  Google Scholar 

  22. Mor, B.: Minmax scheduling problems with common due-date and completion time penalty. J. Comb. Optim. 38, 50–71 (2019)

    Article  MathSciNet  Google Scholar 

  23. Mosheiov, G., Sidney, J.B.: Scheduling with general job-dependent learning curves. Eur. J. Oper. Res. 147(3), 665–670 (2003)

    Article  MathSciNet  Google Scholar 

  24. Panwalker, S.S., Smith, M.L., Seidmann, A.: Common due-date assignment to minimize total penalty for the one machine scheduling problem. Oper. Res. 30, 391–399 (1982)

    Article  Google Scholar 

  25. 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. 149, 106803 (2020)

    Article  Google Scholar 

  26. Seidmann, A., Panwalkar, S.S., Smith, M.L.: Optimal assignment of due-dates for a single processor scheduling problem. Int. J. Prod. Res. 19(4), 393–399 (1981)

    Article  Google Scholar 

  27. Wang, J.-B.: A note on scheduling problems with learning effect and deteriorating jobs. Int. J. Syst. Sci. 37(12), 827–833 (2006)

    Article  MathSciNet  Google Scholar 

  28. Wang, J.-B.: Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect. Comput. Ind. Eng. 55, 584–591 (2008)

    Article  Google Scholar 

  29. Wang, L.-Y., Huang, X., Liu, W.-W., Wu, Y.-B., Wang, J.-B.: Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times. RAIRO-Oper. Res. 55, 2747–2758 (2021)

    Article  MathSciNet  Google Scholar 

  30. Wang, J.-B., Li, J.-X.: Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects. Appl. Math. Model. 35, 1388–1395 (2011)

    Article  MathSciNet  Google Scholar 

  31. Wang, J.-B., Lv, D.-Y., Xu, J., Ji, P., Li, F.: Bicriterion scheduling with truncated learning effects and convex controllable processing times. Int. Trans. Oper. Res. 28, 1573–1593 (2021)

    Article  MathSciNet  Google Scholar 

  32. Wang, X.-R., Wang, J.-B., Gao, W.-J., Huang, X.: Scheduling with past-sequence-dependent setup times and learning effects on a single machine. Int. J. Adv. Manuf. Technol. 48, 739–746 (2010)

    Article  Google Scholar 

  33. Wang, J.-B., Xu, J.-X., Guo, F., Liu, M.: Single-machine scheduling problems with job rejection, deterioration effects and past-sequence-dependent setup times. Engineering Optimization. https://doi.org/10.1080/0305215X.2021.1876041

  34. Wang, D.-J., Yin, Y., Xu, J., Wu, W.-H., Cheng, S.-R., Wu, C.-C.: Some due date determination scheduling problems with two agents on a single machine. Int. J. Prod. Econ. 168, 81–90 (2015)

    Article  Google Scholar 

  35. Yin, N.: Single-machine due-window assignment resource allocation scheduling with job-dependent learning effect. J. Appl. Math. Comput. 56, 715–725 (2018)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This research was supported by the National Natural Science Foundation of China (71903020 and 71672019) and the Natural Science Foundation of Liaoning Province, China (20180550743).

Author information

Authors and Affiliations

  1. College of Mechanical and Electronic Engineering, Dalian Minzu University, Dalian, 116600, People’s Republic of China

    Wanlei Wang

Authors
  1. Wanlei Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wanlei Wang.

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

Wang, W. Single-machine due-date assignment scheduling with generalized earliness-tardiness penalties including proportional setup times. J. Appl. Math. Comput. 68, 1013–1031 (2022). https://doi.org/10.1007/s12190-021-01555-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12190-021-01555-4

Keywords

Mathematics Subject Classification

Search

Navigation