nach oben

Journal of Combinatorial Optimization

Erschienen in:

07.06.2019

Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection

verfasst von: Shi-Sheng Li, Ren-Xia Chen, Qi Feng, Cheng-Wen Jiao

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We study a parallel-machine scheduling problem in which job rejection is allowed and the actual processing time of a job depends on the sum of certain parameters associated with the jobs scheduled earlier. The goal is to minimize the sum of the makespan of the accepted jobs and total rejection penalty of the rejected jobs. When the number of machines is fixed, we develop an exact dynamic programming algorithm and a fully polynomial-time approximation scheme for solving it. When the number of machines is restricted to one, we reformulate the problem as a variant of a half-product problem, which allows us to design a fully polynomial-time approximation scheme with the best possible running time.

Vorheriger Artikel Integer programming formulations for the shared multicast tree problem

Nächster Artikel Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Badics T, Boros E (1998) Minimization of half-products. Math Oper Res 33:649–660MathSciNetCrossRefMATH

Browne S, Yechiali U (1990) Scheduling deteriorating jobs on a single processor. Oper Res 38:495–498CrossRefMATH

Cesaret B, Oǧuz C, Salman FS (2012) A tabu search algorithm for order acceptance and scheduling. Comput Oper Res 39:1197–1205CrossRef

Cheng YS, Sun SJ (2009) Scheduling linear deteriorating jobs with rejection on a single machine. Eur J Oper Res 194:18–27MathSciNetCrossRefMATH

Cheng TCE, Ding Q, Lin BMT (2004) A concise survey of scheduling with time-dependent processing times. Eur J Oper Res 152:1–13MathSciNetCrossRefMATH

Erel E, Ghosh JB (2008) FPTAS for half-products minimization with scheduling applications. Discrete Appl Math 156:3046–3056MathSciNetCrossRefMATH

Gawiejnowicz S (2008) Time-dependent scheduling. Springer, BerlinCrossRefMATH

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

Huang X, Wang JJ (2015) Machine scheduling problems with a position-dependent deterioration. Appl Math Model 39:2897–2908MathSciNetCrossRef

Janiak A, Krysiak T, Trela R (2011) Scheduling problems with learning and ageing effects: a survey. Decis Mak Manuf Serv 5:19–36MathSciNetMATH

Kellerer H, Strusevich VA (2010) Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack. Int J Found Comput Sci 21:357–383MathSciNetCrossRefMATH

Kellerer H, Strusevich VA (2016) Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications. Ann Oper Res 240:39–94MathSciNetCrossRefMATH

Kellerer H, Rustogi K, Strusevich VA (2013) Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance. J Schedul 16:675–683MathSciNetCrossRefMATH

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

Kovalyov MY, Kubiak W (1998) A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs. J Heuristics 3:287–297CrossRefMATH

Kovalyov MY, Kubiak W (1999) A fully polynomial approximation scheme for the weighted earliness-tardiness problem. Oper Res 47:757–761MathSciNetCrossRefMATH

Li SS, Chen RX (2017) Common due date assignment and cumulative deterioration scheduling on a single machine. Eng Optim 49:976–989MathSciNetCrossRef

Li SS, Yuan JJ (2010) Parallel-machine scheduling with deteriorating jobs and rejection. Theor Comput Sci 411:3642–3650MathSciNetCrossRefMATH

Liu P, Yi N, Zhou X, Gong H (2013) Scheduling two agents with sum-of-processing-times-based deterioration on a single machine. Appl Math Comput 219:8848–8855MathSciNetMATH

Rustogi K, Strusevich VA (2017) Single machine scheduling with a generalized job-dependent cumulative effect. J Schedul 20:583–592MathSciNetCrossRefMATH

Shabtay D, Gasper N, Kaspi M (2013) A survey on scheduling problems with rejection. J Schedul 16:3–28CrossRefMATH

Slotnick SA (2011) Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res 212:1–11MathSciNetCrossRef

Strusevich VA, Rustogi K (2017) Scheduling with time-changing effects and rate-modifying activities. Springer, ChamCrossRefMATH

Titel: Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection
verfasst von: Shi-Sheng Li
Ren-Xia Chen
Qi Feng
Cheng-Wen Jiao
Publikationsdatum: 07.06.2019
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2019
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00429-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2019

On perfect Roman domination number in trees: complexity and bounds

Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks

Characterizations of matroids with an element lying in a restricted number of circuits

Unbounded parallel-batch scheduling under agreeable release and processing to minimize total weighted number of tardy jobs

A lower bound for online rectangle packing

Integer programming formulations for the shared multicast tree problem

Premium Partner