nach oben

Journal of Combinatorial Optimization

Erschienen in:

25.01.2016

Two-agent scheduling of time-dependent jobs

verfasst von: Cheng He, Joseph Y.-T. Leung

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider the problem of scheduling deteriorating jobs or shortening jobs with two agents A and B. We are interested in generating all Pareto-optimal schedules for the two criteria: (1) the total completion time of the jobs in A and the maximum cost of the jobs in B, and (2) the maximum cost of the jobs in A and the maximum cost of the jobs in B. We show that all Pareto-optimal schedules for both problems can be generated in polynomial time, whether the jobs are deteriorating or shortening.

Vorheriger Artikel The Weight Function Lemma for graph pebbling

Nächster Artikel A note on (s, t)-relaxed L(2, 1)-labeling of graphs

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, Mirchani PB, Pacciarelli D, Pacifici A (2004) Scheduling problems with two competing agents. Oper Res 52:229–242MathSciNetCrossRefMATH

Agnetis A, Pacciarelli D, Pacifici A (2007) Multi-agent single machine scheduling. Ann Oper Res 150:3–15MathSciNetCrossRefMATH

Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A (2014) Multiagent scheduling: models and algorithms. Springer, BerlinCrossRefMATH

Alidaee B, Womer NK (1999) Scheduling with time dependent processing times: review and extensions. J Oper Res Soc 50:711–720CrossRefMATH

Baker KR, Smith JC (2003) A multiple criterion model for machine scheduling. J Sched 6:7–16MathSciNetCrossRefMATH

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

Brucker P (2001) Scheduling algorithms, 3rd edn. Springer, BerlinCrossRefMATH

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

Cheng TCE, Ng CT, Yuan JJ (2006) Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theor Comput Sci 362:273–281MathSciNetCrossRefMATH

Cheng TCE, Ng CT, Yuan JJ (2008) Multi-agent scheduling on a single machine with max-form criteria. Eur J Oper Res 188:603–609MathSciNetCrossRefMATH

Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326MathSciNetCrossRefMATH

Gupta JND, Gupta SK (1988) Single facility scheduling with nonlinear processing times. Comput Ind Eng 14:387–393MathSciNetCrossRef

Ho KIJ, Leung JY-T, Wei W-D (1993) Complexity of scheduling tasks with time-dependent execution times. Inf Process Lett 48:315–320MathSciNetCrossRefMATH

Hoogeveen H (2005) Multicriteria scheduling. Eur J Oper Res 167:592–623MathSciNetCrossRefMATH

Leung JY-T, Pinedo M, Wan G (2010) Competitive two-agent scheduling and its applications. Oper Res 58:458–469MathSciNetCrossRefMATH

Liu P, Tang L (2008) Two-agent scheduling with linear deteriorating jobs on single-machine. Lect Notes Comput Sci 5029:642–650MathSciNetCrossRefMATH

Liu P, Yi N, Zhou XY (2011) Two-agent single-machine scheduling problems under increasing linear deterioration. Appl Math Model 35:2290–2296MathSciNetCrossRefMATH

Ng CT, Cheng TCE, Bachman A, Janiak A (2002) Three scheduling problems with deteriorating jobs to minimize the total completion time. Inf Process Lett 81:327–333MathSciNetCrossRefMATH

Ng CT, Cheng TCE, Yuan JJ (2006) A note on the complexity of the problem of two-agent scheduling on a single machine. J Comb Optim 12:387–394MathSciNetCrossRefMATH

Wan G, Vakati SR, Leung JY-T, Pinedo M (2010) Scheduling two agents with controllable processing times. Eur J Oper Res 205:528–539MathSciNetCrossRefMATH

Wang JB (2010) A note on single-machine scheduling with decreasing time-dependent job processing times. Appl Math Model 34:294–300MathSciNetCrossRefMATH

Yin YQ, Cheng SR, Wu CC (2012) Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Inf Sci 189:282–292MathSciNetCrossRefMATH

Yuan JJ, Shang WP, Feng Q (2005) A note on the scheduling with two families of jobs. J Sched 8:537–542MathSciNetCrossRefMATH

Zhao CL, Zhang QL, Tang HY (2003) Scheduling problems under linear deterioration. Acta Autom Sin 29:531–535MathSciNet

Titel: Two-agent scheduling of time-dependent jobs
verfasst von: Cheng He
Joseph Y.-T. Leung
Publikationsdatum: 25.01.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-9994-y

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 2/2017

Single-machine scheduling with production and rejection costs to minimize the maximum earliness

Distance domination in graphs with given minimum and maximum degree

A note on orientation and chromatic number of graphs

Triple-solution approach for the strip packing problem with two-staged patterns

Online scheduling to minimize the total weighted completion time plus the rejection cost

The adjacent vertex distinguishing total chromatic numbers of planar graphs with