中文

Operations Research Transactions >

2017 , Vol. 21 >Issue 1: 13 - 22

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

Two-agent scheduling problem about total late  work on a single machine

Expand
  • 1. College of Mathematics Science, Chongqing Normal University, Chongqing 400047, China

Received date: 2015-11-12

  Online published: 2017-03-15

Fold

Abstract

We consider two-agent scheduling problem about total late work on a single machine. The first agent has total late work as its objective function, while the second agent considers either the total complete time or the number of tardy jobs as its objective function. The goal is to find a schedule that minimize the objective of the first agent while keeping the objective of the second agent cannot exceed a giving upper bound. We present a pseudo-polynomial time algorithm for these two scheduling problem, respectively.

Key words： scheduling; two-agent; total late work; polynomial programming algorithm

Cite this article

MA Lu, ZHANG Xingong . Two-agent scheduling problem about total late  work on a single machine[J]. Operations Research Transactions, 2017 , 21(1) : 13 -22 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.01.002

References

[1] Agnetis A, Mirchandani P B, Pacciarelli D, et al. Scheduling problems with two competing agents [J]. Operations Research, 2004, 52(2): 229-242.
[2] Joseph Y T L, Pinedo M, Wan G H. Competitive two-agent scheduling and its applications [J]. Operations Research, 2010, 52(8): 458-469.
[3] Perez-Gonzalez P, Framinan J M. A common framework and taxonomy for multi-criteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems [J]. European Journal of Operational Research, 2014, 235(1): 1-16.
[4] 万龙. 有关单机两代理排序问题的两个结果 [J]. 运筹学学报, 2015, 19(2): 54-60.
[5] Potts C N, Van Wassenhove L N. Single machine scheduling to minimize total late work [J]. Operations Research, 1992, 40(3): 586-595.
[6] 戴秦, 郑兴山, 张新功, 等. 总迟后相关的两个工况代理的单机排序问题 [J]. 工业 工程与管理, 2014, 19(6): 78-88.
[7] Sterna M. A survey of scheduling problem with late work criteria [J]. Omega, 2011, 39: 120-129.
[8] Graham P L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic machine scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5(1): 287-326.
[9] Peter B. Scheduling Algorithms [M].  Springer-Verlag Berlin Heidelberg New work, 2006.
[10] Ng C T, Cheng T C E, Yuan J J. A note on the complexity of two-agent scheduling on a single machine [J]. Journal of Combinatorial Optimization, 2006, 12: 387-394.
Options
Outlines

/

〈 〉