Skip to main content
Erschienen in: Journal of Combinatorial Optimization 1/2019

28.11.2018

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

verfasst von: Baruch Mor

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Agnetis A, Mosheiov G (2017) Scheduling with job-rejection and position-dependent processing times on proportionate flowshops. Optim Lett 11:885–892MathSciNetCrossRefMATH Agnetis A, Mosheiov G (2017) Scheduling with job-rejection and position-dependent processing times on proportionate flowshops. Optim Lett 11:885–892MathSciNetCrossRefMATH
Zurück zum Zitat Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A (2014) Multiagent scheduling. Springer, BerlinCrossRefMATH Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A (2014) Multiagent scheduling. Springer, BerlinCrossRefMATH
Zurück zum Zitat Biskup D (1999) Single-machine scheduling with learning considerations. Eur J Oper Res 115:173–178CrossRefMATH Biskup D (1999) Single-machine scheduling with learning considerations. Eur J Oper Res 115:173–178CrossRefMATH
Zurück zum Zitat Biskup D, Cheng TCE (1999a) Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties. Eng Optim 31:329–336CrossRef Biskup D, Cheng TCE (1999a) Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties. Eng Optim 31:329–336CrossRef
Zurück zum Zitat Biskup D, Cheng TCE (1999b) Multiple-machine scheduling with earliness, tardiness and completion time penalties. Comput Oper Res 26:45–57MathSciNetCrossRefMATH Biskup D, Cheng TCE (1999b) Multiple-machine scheduling with earliness, tardiness and completion time penalties. Comput Oper Res 26:45–57MathSciNetCrossRefMATH
Zurück zum Zitat Dolgui A, Gordon VS, Strusevich VA (2012) Single machine scheduling with precedence constraints and positionally dependent processing times. Comput Oper Res 39:1218–1224MathSciNetCrossRefMATH Dolgui A, Gordon VS, Strusevich VA (2012) Single machine scheduling with precedence constraints and positionally dependent processing times. Comput Oper Res 39:1218–1224MathSciNetCrossRefMATH
Zurück zum Zitat Gerstl E, Mosheiov G (2012) Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Inf Process Lett 112:743–747MathSciNetCrossRefMATH Gerstl E, Mosheiov G (2012) Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Inf Process Lett 112:743–747MathSciNetCrossRefMATH
Zurück zum Zitat 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–156MathSciNetCrossRefMATH 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–156MathSciNetCrossRefMATH
Zurück zum Zitat Gordon VS, Strusevich VA (2009) Single machine scheduling and due date assignment with positionally dependent processing times. Eur J Oper Res 198(1):57–62MathSciNetCrossRefMATH Gordon VS, Strusevich VA (2009) Single machine scheduling and due date assignment with positionally dependent processing times. Eur J Oper Res 198(1):57–62MathSciNetCrossRefMATH
Zurück zum Zitat 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–25MathSciNetCrossRefMATH 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–25MathSciNetCrossRefMATH
Zurück zum Zitat Janiak A, Janiak WA, Krysial T, Kwiatkowski T (2015) A survey on scheduling problems with due windows. Eur J Oper Res 242(2):347–357MathSciNetCrossRefMATH Janiak A, Janiak WA, Krysial T, Kwiatkowski T (2015) A survey on scheduling problems with due windows. Eur J Oper Res 242(2):347–357MathSciNetCrossRefMATH
Zurück zum Zitat 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–1010CrossRefMATH 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–1010CrossRefMATH
Zurück zum Zitat 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–602CrossRef 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–602CrossRef
Zurück zum Zitat Mor B, Mosheiov G (2012a) Heuristics for scheduling problems with an unavailability constraint and position-dependent processing times. Comput Ind Eng 62(4):908–916CrossRef Mor B, Mosheiov G (2012a) Heuristics for scheduling problems with an unavailability constraint and position-dependent processing times. Comput Ind Eng 62(4):908–916CrossRef
Zurück zum Zitat Mor B, Mosheiov G (2012b) Minmax scheduling problems with common flow-allowance. J Oper Res Soc 63(9):1284–1293CrossRef Mor B, Mosheiov G (2012b) Minmax scheduling problems with common flow-allowance. J Oper Res Soc 63(9):1284–1293CrossRef
Zurück zum Zitat Mor B, Mosheiov G (2015) Scheduling a deteriorating maintenance activity and due-window assignment. Comput Oper Res 57:33–40MathSciNetCrossRefMATH Mor B, Mosheiov G (2015) Scheduling a deteriorating maintenance activity and due-window assignment. Comput Oper Res 57:33–40MathSciNetCrossRefMATH
Zurück zum Zitat 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–1531CrossRef 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–1531CrossRef
Zurück zum Zitat Mosheiov G (2011) Proportionate flowshops with general position-dependent processing times. Inf Process Lett 111(4):174–177MathSciNetCrossRefMATH Mosheiov G (2011) Proportionate flowshops with general position-dependent processing times. Inf Process Lett 111(4):174–177MathSciNetCrossRefMATH
Zurück zum Zitat Mosheiov G, Sarig A (2008) A due-window assignment problem with position-dependent processing times. J Oper Res Soc 59:997–1003CrossRefMATH Mosheiov G, Sarig A (2008) A due-window assignment problem with position-dependent processing times. J Oper Res Soc 59:997–1003CrossRefMATH
Zurück zum Zitat 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–399CrossRefMATH 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–399CrossRefMATH
Zurück zum Zitat Schmenner RW (1988) The merit of making things fast. Sloan Manag Rev 30:7–11 Schmenner RW (1988) The merit of making things fast. Sloan Manag Rev 30:7–11
Zurück zum Zitat 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–74MathSciNetCrossRefMATH 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–74MathSciNetCrossRefMATH
Zurück zum Zitat Wang J-B, Wang J-J (2013) Single-machine scheduling with precedence constraints and position-dependent processing times. Appl Math Model 37:649–658MathSciNetCrossRefMATH Wang J-B, Wang J-J (2013) Single-machine scheduling with precedence constraints and position-dependent processing times. Appl Math Model 37:649–658MathSciNetCrossRefMATH
Zurück zum Zitat 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–422MathSciNetMATH 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–422MathSciNetMATH
Zurück zum Zitat Zhong X, Pan Z, Jiang D (2017) Scheduling with release times and rejection on two parallel machines. J Combin Optim 33:934–944MathSciNetCrossRefMATH Zhong X, Pan Z, Jiang D (2017) Scheduling with release times and rejection on two parallel machines. J Combin Optim 33:934–944MathSciNetCrossRefMATH
Zurück zum Zitat 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–3490CrossRef 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–3490CrossRef
Metadaten
Titel
Minmax scheduling problems with common due-date and completion time penalty
verfasst von
Baruch Mor
Publikationsdatum
28.11.2018
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 1/2019
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-018-0365-8

Weitere Artikel der Ausgabe 1/2019

Journal of Combinatorial Optimization 1/2019 Zur Ausgabe