nach oben

Journal of Combinatorial Optimization

Erschienen in:

20.01.2021

Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work

verfasst von: Ruyan He, Jinjiang Yuan, C. T. Ng, T. C. E. Cheng

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider the single-machine preemptive Pareto-scheduling problem with two competing agents A and B, where agent A wants to minimize the number of its jobs (the A-jobs) that is tardy, while agent B wants to minimize the total late work of its jobs (the B-jobs). We provide an \(O(nn_{A}\log n_{A}+n_B\log n_B)\)-time algorithm that generates all the Pareto-optimal points, where \(n_A\) is the number of the A-jobs, \(n_B\) is the number of the B-jobs, and \(n=n_A+n_B\).

Vorheriger Artikel On sufficient topological indices conditions for properties of graphs

Nächster Artikel Italian domination in the Cartesian product of paths

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

Nur mit Berechtigung zugänglich

Agnetis A, Mirchandani PB, Pacciarelli D, Pacifici A (2004) Scheduling problems with two competing agents. Oper Res 52:229–242MathSciNetCrossRef

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

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

Blazewicz J, Finke G (1987) Minimizing mean weighted execution time loss on identical and uniform processors. Inf Process Lett 24:259–263MathSciNetCrossRef

Brucker P (2001) Scheduling algorithms. Springer, BerlinCrossRef

Chen B, Potts CN, Woeginger GJ (1998) A review of machine scheduling: complexity, algorithms and approximability. In: Du DZ, Pardalos PM (eds) Handbook of combinatorial optimization. Kluwer Academic Publishers, Dordrecht, pp 21–169

Chen RB, Yuan JJ, Ng CT, Cheng TCE (2019a) Single-machine scheduling with deadlines to minimize the total weighted late work. Naval Res Logist 66:582–595MathSciNetCrossRef

Chen RB, Yuan JJ, Gao Y (2019b) The complexity of CO-agent scheduling to minimize the total completion time and total number of tardy jobs. J Sched 22:581–593MathSciNetCrossRef

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

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

Gao Y, Yuan JJ (2017) Bi-criteria Pareto-scheduling on a single machine with due indices and precedence constraints. Discrete Optim 25:105–119MathSciNetCrossRef

Gao Y, Yuan JJ, Ng CT, Cheng TCE (2020) A note on competing-agent Pareto-scheduling. Optim Lett. https://doi.org/10.1007/s11590-020-01576-1

Hariri AMA, Potts CN, Van Wassenhove LN (1995) Single machine scheduling to minimize total weighted late work. ORSA J Comput 7:232–242CrossRef

He RY, Yuan JJ (2020) Two-agent preemptive Pareto-scheduling to minimize late work and other criteria. Mathematics 8:1517CrossRef

Lawler EL (1983) Recent results in the theory of machine scheduling. In: Bachem A et al (eds) Mathematical programming-the state of the art. Springer, Berlin, pp 202–234CrossRef

Lee WC, Wang WJ, Shiau YR, Wu CC (2010) A single-machine scheduling problem with two-agent and deteriorating jobs. Appl Math Model 34:3098–3107MathSciNetCrossRef

Leung JYT, Pinedo M, Wan G (2010) Competitive Two-Agent Scheduling and Its Applications. Oper Res 58:458–469MathSciNetCrossRef

Li SS, Yuan JJ (2020) Single-machine scheduling with multi-agents to minimize total weighted late work. J Sched 23:497–512MathSciNetCrossRef

Liu P, Gu M, Li G (2019) Two-agent scheduling on a single machine with release dates. Comput Oper Res 111:35–42MathSciNetCrossRef

Moore JM (1968) An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs. Manage Sci 15:102–109CrossRef

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

Oron D, Shabtay D, Steiner G (2015) Single machine scheduling with two competing agents and equal jobs processing times. Eur J Oper Res 244:86–99MathSciNetCrossRef

Potts CN, Van Wassenhove LN (1991a) Single machine scheduling to minimize total late work. Oper Res 40:586–595MathSciNetCrossRef

Potts CN, Van Wassenhove LN (1991b) Approximation algorithms for scheduling a single machine to minimize total late work. Oper Res Lett 11:261–266MathSciNetCrossRef

Sterna M (2011) A survey of scheduling problems with late work criteria. Omega 39:120–129CrossRef

T’kindt V, Billaut JC (2006) Multicriteria scheduling: theory, models and algorithms, 2nd edn. Springer, Berlin

Wan L, Yuan JJ, Wei LJ (2016) Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost. Appl Math Comput 273:912–923MathSciNetMATH

Yuan JJ (2018) Complexities of four problems on two-agent scheduling. Optimization Letters 12:763–780MathSciNetCrossRef

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

Yuan JJ, Lin YX (2005b) Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria. Eur J Oper Res 164:851–855CrossRef

Yuan JJ (2016) Complexities of some problems on multi-agent scheduling on a single machine. J Oper Res Soc China 4:379–384MathSciNetCrossRef

Zhang XG, Wang Y (2017) Two-agent scheduling problems on a single-machine to minimize the total weighted late work. J Combin Optim 33:945–955MathSciNetCrossRef

Zhang Y, Yuan JJ (2019) A note on a two-agent scheduling problem related to the total weighted late work. J Combin Optim 37:989–999MathSciNetCrossRef

Zhang Y, Yuan JJ, Ng CT, Cheng TCE (2020) Pareto-optimization of three-agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work. Naval Res Logist. https://doi.org/10.1002/nav.21961

Zhao QL, Yuan JJ (2019) A note on single-machine scheduling to tradeoff between the number of tardy jobs and the start time of machine. Oper Res Lett 47:607–610MathSciNetCrossRef

Zhao QL, Yuan JJ (2020) Bicriteria scheduling of equal length jobs on uniform parallel machines. J Combin Optim 39:637–661MathSciNetCrossRef

Titel: Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work
verfasst von: Ruyan He
Jinjiang Yuan
C. T. Ng
T. C. E. Cheng
Publikationsdatum: 20.01.2021
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2021
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-021-00697-2

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/2021

Application of multi-objective optimization algorithm for siting and sizing of distributed generations in distribution networks

Differentially private approximate aggregation based on feature selection

Dominating set of rectangles intersecting a straight line

Italian domination in the Cartesian product of paths

The balanced double star has maximum exponential second Zagreb index

Group level social media popularity prediction by MRGB and Adam optimization