关于总误工损失的两个代理单机排序问题

doi:10.15960/j.cnki.issn.1007-6093.2017.01.002

Abstract

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, doi: 10.15960/j.cnki.issn.1007-6093.2017.01.002.

share this article

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2017.01.002

https://www.ort.shu.edu.cn/EN/Y2017/V21/I1/13

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.

Related Articles 15

[1]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[3]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[4]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[5]	GOU Yan, DAI Qin, ZHANG Xingong. Scheduling problem with time-and-position-dependent effect on two parallel machines environments [J]. Operations Research Transactions, 2019, 23(4): 86-94.
[6]	LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time [J]. Operations Research Transactions, 2019, 23(4): 95-104.
[7]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[8]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[9]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[10]	CHEN Qiuhong, ZHANG Xingong. Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine [J]. Operations Research Transactions, 2019, 23(1): 61-71.
[11]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[12]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[13]	ZHAO Xiaocheng, LI Dagang. Parallel machine scheduling with machine and human eligibility restrictions [J]. Operations Research Transactions, 2018, 22(3): 99-108.
[14]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.
[15]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.

Metrics

Viewed

Full text

Abstract

Comments

Abstract
References
Related Articles
Recommended Articles
Metrics
Comments

TOP

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

PDF

Knowledge