带有固定区间的单机双代理可中断总误工问题

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

Operations Research Transactions ›› 2019, Vol. 23 ›› Issue (1): 61-71.doi: 10.15960/j.cnki.issn.1007-6093.2019.01.007

Previous Articles Next Articles

Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine

CHEN Qiuhong, ZHANG Xingong^*

College of Mathematics Science, Chongqing Normal University, Chongqing 400047, China

Received:2017-10-11 Online:2019-03-15 Published:2019-03-15

Abstract

Abstract:

This paper considers two agent scheduling problems with fixed time windows on a single machine. The jobs of the first agent might be preemptive. There exists agreeable condition with release time and due data. The objective function is to minimize the total tardiness. The focus is to find an optimal sequence that minimizes the objective of the first agent, while keeping all jobs of the second agent schedule within fixed time windows. By block principle, we present a pseudo-polynomial time dynamic programming algorithm when fixed time window equals the processing time. If the fixed time windows is larger than the processing time, we give the time complexity of the proposed problem.

Key words: single scheduling, two-agent, total tardiness, fixed time windows

CLC Number:

O223

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.

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] Agnetis A, Pacciarelli D, Pacifici A. Multi-agent single machine scheduling[J]. Annals of Operations Research, 2007, 150(1):3-15.
[3] 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(2):603-609.
[4] Leung J Y T, Pinedo M, Wan G H. Competitive two-agent scheduling and its applications[J]. Operations Research, 2010, 58(2):458-469.
[5] Perez-Gonzalez P, Framinan J M. A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs:Multi-agent scheduling problems[J]. European Journal of Operational Research, 2014, 235(1):1-16.
[6] 马露, 张新功. 关于总误工损失的两个代理单机排序问题[J]. 运筹学学报, 2017, 21(1):13-22.
[7] Lawler E L. A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness[J]. Annals of Discrete Mathematics, 1977, 1:331-342.
[8] Koulamas C, Kyparisis G J. Single machine scheduling with release times, deadlines and tardiness objectives[J]. European Journal of Operational Research, 2001, 133(2):447-453.
[9] Tian Z J, Ng C T, Cheng T C E. An O(n²) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness[J]. Journal of Scheduling, 2006, 9(4):343-364.
[10] Tian Z J, Ng C T, Cheng T C E. Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness[J]. Operations Research Letters, 2009, 37(5):368-374.
[11] Graham R 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:287-326.
[12] Pinedo M L. Scheduling:Theory, Algorithms, and Systems[M]. New Jersey:Prentice Hall, 1955.
[13] Baker K R, Lawler E L, Lenstra J K, et al. Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints[J]. Operations Research, 1983, 31(2):381-386.
[14] Brucker P. Scheduling Algorithms[M]. Berlin:Springer-Verlag, 2007.

Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	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.
[2]	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.
[3]	WAN Long. Two results for single-machine two-agent scheduling problems [J]. Operations Research Transactions, 2015, 19(2): 54-60.