An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times

Ming Liu; Chengbin Chu; Yinfeng Xu; Feifeng Zheng

doi:10.1007/s11590-009-0163-4

An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times

Ming Liu
, Chengbin Chu
, Yinfeng Xu
, Feifeng Zheng

School of Management

Xi'an Jiaotong University
Ecole Centrale Paris

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

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 p_1,j and p_2,j denote the processing time of a job J_j on the two machines M₁ and M₂, respectively. Bounded processing times mean that 1 ≤ p_i,j ≤ α (i = 1, 2) for each job J_j, where α ≥ 1 is a constant number. We propose an optimal online algorithm with a competitive ratio.

Original language	English
Pages (from-to)	227-237
Number of pages	11
Journal	Optimization Letters
Volume	4
Issue number	2
DOIs	https://doi.org/10.1007/s11590-009-0163-4
State	Published - 2010

Keywords

Bounded processing times
Competitive analysis
Online algorithm
Open shop scheduling

Access to Document

10.1007/s11590-009-0163-4

Cite this

@article{926a5c27414c4426b76310e7f448e649,

title = "An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times",

abstract = "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.",

keywords = "Bounded processing times, Competitive analysis, Online algorithm, Open shop scheduling",

author = "Ming Liu and Chengbin Chu and Yinfeng Xu and Feifeng Zheng",

year = "2010",

doi = "10.1007/s11590-009-0163-4",

language = "英语",

volume = "4",

pages = "227--237",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "2",

}

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 -

An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this