TY - JOUR
T1 - An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times
AU - Liu, Ming
AU - Chu, Chengbin
AU - Xu, Yinfeng
AU - Zheng, Feifeng
PY - 2010
Y1 - 2010
N2 - This paper deals with a two-machine open shop scheduling problem. The objective is to minimize the makespan. Jobs arrive over time. We study preemption-resume model, i.e., the currently processed job may be preempted at any moment in necessary and be resumed some time later. Let p1,j and p2,j denote the processing time of a job Jj on the two machines M1 and M2, respectively. Bounded processing times mean that 1 ≤ pi,j ≤ α (i = 1, 2) for each job Jj, where α ≥ 1 is a constant number. We propose an optimal online algorithm with a competitive ratio.
AB - This paper deals with a two-machine open shop scheduling problem. The objective is to minimize the makespan. Jobs arrive over time. We study preemption-resume model, i.e., the currently processed job may be preempted at any moment in necessary and be resumed some time later. Let p1,j and p2,j denote the processing time of a job Jj on the two machines M1 and M2, respectively. Bounded processing times mean that 1 ≤ pi,j ≤ α (i = 1, 2) for each job Jj, where α ≥ 1 is a constant number. We propose an optimal online algorithm with a competitive ratio.
KW - Bounded processing times
KW - Competitive analysis
KW - Online algorithm
KW - Open shop scheduling
UR - https://www.scopus.com/pages/publications/77955087730
U2 - 10.1007/s11590-009-0163-4
DO - 10.1007/s11590-009-0163-4
M3 - 文章
AN - SCOPUS:77955087730
SN - 1862-4472
VL - 4
SP - 227
EP - 237
JO - Optimization Letters
JF - Optimization Letters
IS - 2
ER -