Top

Journal of Combinatorial Optimization

Published in:

20-01-2021

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

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

Published in: Journal of Combinatorial Optimization | Issue 2/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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\).

previous article On sufficient topological indices conditions for properties of graphs

next article Italian domination in the Cartesian product of paths

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

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

Title: Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work
Authors: Ruyan He
Jinjiang Yuan
C. T. Ng
T. C. E. Cheng
Publication date: 20-01-2021
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 2/2021
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-021-00697-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2021

Secure domination in rooted product graphs

Research on single-machine scheduling with position-dependent weights and past-sequence-dependent delivery times

Application of optimization methods in the closed-loop supply chain: a literature review

Italian domination in the Cartesian product of paths

Zero forcing versus domination in cubic graphs

Approximation algorithm for the multicovering problem

Premium Partner