Top

Journal of Combinatorial Optimization

Published in:

15-04-2016

Two-agent scheduling problems on a single-machine to minimize the total weighted late work

Authors: Zhang Xingong, Wang Yong

Published in: Journal of Combinatorial Optimization | Issue 3/2017

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

search-config

AI-assisted search

Off

Abstract

In this paper, two-agent scheduling problems are presented. The different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. The objective functions we consider are the total weighted late work and the maximum cost. The problem is to find a schedule that minimizes the objective function of agent A, while keeping the objective function of agent B cannot exceed a given bound U. Some different scenarios are presented by depending on the objective function of each agent. We address the complexity of those problems, and present the optimal polynomial time algorithms or pseudo-polynomial time algorithm to solve the scheduling problems, respectively.

previous article Scheduling with release times and rejection on two parallel machines

next article Construction independent spanning trees on locally twisted cubes in parallel

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

Abasian F, Ranjbar M, Salari M, Davari M (2014) Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays. Appl Math Model 38:3975–3986

Agnetis A, Mirchandani 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

Blazewicz J (1984) Scheduling preemptible tasks on parallel processors with information loss. Tech Sci Inf 3(6):415–420MATH

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

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

Fan BQ, Cheng TCE (2016) Two-agent scheduling in a flowshop. Eur J Oper Res. doi:10.1016/j.ejor.2016.01.009 MathSciNetMATH

Feng Q, Yuan JJ, Liu HL, He C (2013) A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives. Appl Math Model 37:7071–7076MathSciNetCrossRef

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

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

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–3107MathSciNetCrossRefMATH

Leung JYT (2004) Minimizing total weighted error for imprecise computation tasks and related problems. In: Leung JYT (ed) Handbook of scheduling: algorithms, models, and performance analysis. CRC Press, Boca Raton, pp 1–16

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

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, 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

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

Perez-Gonzalez P, Framinan JM (2014) A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. Eur J Oper Res 235:1–16MathSciNetCrossRefMATH

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

Song YY (2011) Research on integrated optimization of hospital supply chain based on multi-agent. Doctoral dissertation in Nanchang University

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

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

Yazdani Sabouni MT, Jolai F (2010) Optimal methods for batch processing problem with makespan and maximum lateness objectives. Appl Math Model 34:314–324MathSciNetCrossRefMATH

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

Zhao KJ, Lu XW (2016) Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan. J Comb Optim 31(1):260–278MathSciNetCrossRefMATH

Title: Two-agent scheduling problems on a single-machine to minimize the total weighted late work
Authors: Zhang Xingong
Wang Yong
Publication date: 15-04-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2017
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-0017-9

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

Augmenting weighted graphs to establish directed point-to-point connectivity

The no-wait job shop with regular objective: a method based on optimal job insertion

Total coloring of 1-toroidal graphs with maximum degree at least 11 and no adjacent triangles

Total completion time minimization in online hierarchical scheduling of unit-size jobs

Construction independent spanning trees on locally twisted cubes in parallel

Power load forecasting by wavelet least squares support vector machine with improved fruit fly optimization algorithm

Premium Partner