中文

Operations Research Transactions >

2015 , Vol. 19 >Issue 2: 54 - 60

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.02.006

Two results for single-machine two-agent scheduling problems

Expand
  • 1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China

Received date: 2014-07-07

  Online published: 2015-06-15

Fold

Abstract

The paper considers two two-agent scheduling problems on a single machine. For the first two-agent scheduling problem, the objective of agent A is to minimize the total weighted completion time of all jobs of agent A while the objective of agent B is to minimize the maximum cost of the jobs of agent B. For the second two-agent scheduling problem, the objective of agent A is to minimize the total completion time of all jobs of agent A while the objective of agent B is to minimize the makespan which is defined as the maximum completion time of all the jobs of agent B. In this paper, we prove that the first problem is NP-hard in the strong sense which improves the current complexity result and design a dynamic programming other than the previous known algorithm for the second problem.

Key words： two-agent scheduling; algorithm complexity; optimal algorithm

Cite this article

WAN Long . Two results for single-machine two-agent scheduling problems[J]. Operations Research Transactions, 2015 , 19(2) : 54 -60 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.006

References

Baker K R, Smith J C. A multiple criterion model for machine scheduling [J]. Journal of Scheduling}, 2003, 6: 7-16.


Agnetis A, Mirchandani P B, Pacciarelli D, et al. Scheduling problems with two competing agents [J]. Operations Research, 2004, 52: 229-242.

Yuan J J, Shang W P, Feng Q. A note on the scheduling with two families of jobs [J]. Journal of Scheduling, 2005, 8: 537-542.

Cheng T C E, Ng  C T, Yuan J J. Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs [J]. Theoretical Computer Science, 2006, 362: 273-281.

Cheng T C E, Ng C T, Yuan J J. Multi-agent scheduling on a single machine with max-form criteria [J]. European Journal of Operational Research, 2008,
188: 603-609.

Li S S, Yuan J J. Unbounded parallel-batching scheduling with two competitive agents [J]. Journal of Scheduling, 2012, 15: 629-640.

Fan B Q, Cheng T C E, Li S S, et al. Bounded parallel-batching scheduling with two competing agents [J]. Journal of Scheduling, 2013, 16: 261-271.

Wan G H, Vakati S R, Leung J Y T, et al. Scheduling two agents with controllable processing times [J]. European Journal of Operational Research, 2010, 205: 528-539.
Yin Y Q, Cheng S R, Wu C C. Scheduling problems with two agents and linear non-increasing deterioration to minimize earliness penalties [J]. Information Sciences, 2012, 189: 282-292.
Leung J Y T, Pinedo M, Wan G H. Competitive two agent scheduling and its applications [J]. Operations Research, 2010, 58: 458-469.
Yuan J J, Ng C T, Cheng T C E. Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness [J]. Journal of Scheduling, 2014, DOI: 10.1007/s10951-013-0360-y.

Wan L, Yuan J J, Geng Z C. A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints [J]. Journal of Scheduling, 2014, DOI: 10.1007/s10951-014-0368-y.

Graham R L, Lawler E L, Lenstra J K, et al. Optimization and heuristic in deterministic sequencing and scheduling: a survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.

Agnetis A, de Pascale G, Pacciarelli D. A Lagrangian approach to single-machine scheduling problems with two competing agents [J]. Journal of Scheduling, 2009, 12: 401-415.

Garey M, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Complete-\\ness [M]. New York: W H Freeman and Company, 1979.

 
Options
Outlines

/

〈 〉