SpringerLink
Log in

Minmax scheduling problems with common due-date and completion time penalty

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

We study the well-known common due-date assignment and scheduling problem and focus on minmax objective functions with position-dependent processing times. In due-date assignment problems, the objective is to find simultaneously the optimal job sequence and due-date that minimize the total earliness, tardiness and due-date related costs. Based on the solution of the problem with position-independent processing times, positional-weights are provided that lead to a simple solution procedure. Two extensions of the basic problem are discussed and solved to optimality. First, we generalize the results of the due-date to the setting of due-window assignment. Second, we study the common due-date problem with completion time penalty. The latter problem is studied with position-independent and position-dependent processing times as well as optional job rejection. For all studied problems, except the last, we introduce efficient polynomial time solutions. In respect to the last problem, considering job-rejection, we prove that it is NP-hard in the ordinary sense and provide an efficient pseudo-polynomial dynamic programming algorithm and extensive numerical study.

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 includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Agnetis A, Mosheiov G (2017) Scheduling with job-rejection and position-dependent processing times on proportionate flowshops. Optim Lett 11:885–892

    Article  MathSciNet  MATH  Google Scholar 

  • Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A (2014) Multiagent scheduling. Springer, Berlin

    Book  MATH  Google Scholar 

  • Baker KR, Scudder GD (1990) Sequencing with earliness and tardiness penalties: a review. Oper Res 38:22–36

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  • Biskup D, Cheng TCE (1999a) Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties. Eng Optim 31:329–336

    Article  Google Scholar 

  • Biskup D, Cheng TCE (1999b) Multiple-machine scheduling with earliness, tardiness and completion time penalties. Comput Oper Res 26:45–57

    Article  MathSciNet  MATH  Google Scholar 

  • Dolgui A, Gordon VS, Strusevich VA (2012) Single machine scheduling with precedence constraints and positionally dependent processing times. Comput Oper Res 39:1218–1224

    Article  MathSciNet  MATH  Google Scholar 

  • Gerstl E, Mosheiov G (2012) Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Inf Process Lett 112:743–747

    Article  MathSciNet  MATH  Google Scholar 

  • Gerstl E, Mor B, Mosheiov G (2017) Minmax scheduling with acceptable lead-times: extensions to position-dependent processing times, due-window and job rejection. Comput Oper Res 83:150–156

    Article  MathSciNet  MATH  Google Scholar 

  • Gordon VS, Strusevich VA (2009) Single machine scheduling and due date assignment with positionally dependent processing times. Eur J Oper Res 198(1):57–62

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Janiak A, Janiak WA, Krysial T, Kwiatkowski T (2015) A survey on scheduling problems with due windows. Eur J Oper Res 242(2):347–357

    Article  MathSciNet  MATH  Google Scholar 

  • Liman SD, Panwalkar SS, Thongmee S (1998) Common due window size and location determination in a single machine scheduling problem. J Oper Res Soc 49(9):1007–1010

    Article  MATH  Google Scholar 

  • Mor B (2018a) Minmax common due-window assignment and scheduling on a single machine with two competing agents. J Oper Res Soc 69(4):589–602

    Article  Google Scholar 

  • Mor B (2018b) Single machine minmax common due-window assignment and scheduling problems with convex resource allocation. Eng Optim. https://doi.org/10.1080/0305215X.2018.1519557

    Google Scholar 

  • Mor B, Mosheiov G (2012a) Heuristics for scheduling problems with an unavailability constraint and position-dependent processing times. Comput Ind Eng 62(4):908–916

    Article  Google Scholar 

  • Mor B, Mosheiov G (2012b) Minmax scheduling problems with common flow-allowance. J Oper Res Soc 63(9):1284–1293

    Article  Google Scholar 

  • Mor B, Mosheiov G (2015) Scheduling a deteriorating maintenance activity and due-window assignment. Comput Oper Res 57:33–40

    Article  MathSciNet  MATH  Google Scholar 

  • Mor B, Mosheiov G (2016) Minimizing maximum cost on a single machine with two competing agents and job rejection. J Oper Res Soc 67:1524–1531

    Article  Google Scholar 

  • Mor B, Mosheiov G (2018) A note: minimizing total absolute deviation of job completion times on unrelated machines with general position-dependent processing times and job-rejection. Ann Oper Res. https://doi.org/10.1007/s1047

    MathSciNet  MATH  Google Scholar 

  • Mor B, Shapira D (2018) Improved algorithms for scheduling on proportionate flowshop with job-rejection. J Oper Res Soc. https://doi.org/10.1080/01605682.2018.1506540

    Google Scholar 

  • Mosheiov G (2011) Proportionate flowshops with general position-dependent processing times. Inf Process Lett 111(4):174–177

    Article  MathSciNet  MATH  Google Scholar 

  • Mosheiov G, Sarig A (2008) A due-window assignment problem with position-dependent processing times. J Oper Res Soc 59:997–1003

    Article  MATH  Google Scholar 

  • Mosheiov G, Sarig A (2009) Minmax scheduling problems with a common due-window. Comput Oper Res 36:1886–1892

    Article  MathSciNet  MATH  Google Scholar 

  • Panwalkar SS, Smith ML, Seidmann A (1982) Common due date assignment to minimize total penalty for the one machine scheduling problem. Oper Res 30(2):391–399

    Article  MATH  Google Scholar 

  • Schmenner RW (1988) The merit of making things fast. Sloan Manag Rev 30:7–11

    Google Scholar 

  • Shabtay D (2014) The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost. Eur J Oper Res 233(1):64–74

    Article  MathSciNet  MATH  Google Scholar 

  • Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16:3–28

    Article  MathSciNet  MATH  Google Scholar 

  • Wang J-B, Wang J-J (2013) Single-machine scheduling with precedence constraints and position-dependent processing times. Appl Math Model 37:649–658

    Article  MathSciNet  MATH  Google Scholar 

  • Xue P, Zhang Y, Yu X (2014) Single-machine scheduling with piece-rate maintenance and interval constrained position-dependent processing times. Appl Math Comput 226:415–422

    MathSciNet  MATH  Google Scholar 

  • Zhang X, **e Q (2015) Single machine group scheduling with position dependent processing times and ready times. Math Probl Eng. https://doi.org/10.1155/2015/206230

    MathSciNet  MATH  Google Scholar 

  • Zhong X, Pan Z, Jiang D (2017) Scheduling with release times and rejection on two parallel machines. J Combin Optim 33:934–944

    Article  MathSciNet  MATH  Google Scholar 

  • Zhu H, Li M, Zhoua Z, You Y (2016) Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity maintenance activity. Int J Prod Res 45(12):3475–3490

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Economics and Business Administration, Ariel University, 40700, Ariel, Israel

    Baruch Mor

Authors
  1. Baruch Mor
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Baruch Mor.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mor, B. Minmax scheduling problems with common due-date and completion time penalty. J Comb Optim 38, 50–71 (2019). https://doi.org/10.1007/s10878-018-0365-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-018-0365-8

Keywords

Search

Navigation