An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan

Ruyan Fu; Edwin Tai Chiu Cheng; Chi To Ng; Jinjiang Yuan

doi:10.1016/j.orl.2013.01.003

An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan

Ruyan Fu, Edwin Tai Chiu Cheng, Chi To Ng, Jinjiang Yuan

Research output: Journal article publication › Journal article › Academic research › peer-review

18 Citations (Scopus)

Abstract

We consider the online scheduling of incompatible job families on an unbounded parallel-batch machine to minimize the makespan, where jobs arrive over time and the number of job families, f, is known in advance. We provide an optimal online algorithm for the problem with a competitive ratio of 1+4f2+1-12f.

Original language	English
Pages (from-to)	216-219
Number of pages	4
Journal	Operations Research Letters
Volume	41
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2013.01.003
Publication status	Published - 1 May 2013

Keywords

Competitive ratio
Incompatible job families
Online scheduling
Parallel-batch machine

ASJC Scopus subject areas

Management Science and Operations Research
Applied Mathematics
Industrial and Manufacturing Engineering
Software

More information

10.1016/j.orl.2013.01.003

Cite this

@article{bec73cd581de499e852d56e3787c3d56,

title = "An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan",

abstract = "We consider the online scheduling of incompatible job families on an unbounded parallel-batch machine to minimize the makespan, where jobs arrive over time and the number of job families, f, is known in advance. We provide an optimal online algorithm for the problem with a competitive ratio of 1+4f2+1-12f.",

keywords = "Competitive ratio, Incompatible job families, Online scheduling, Parallel-batch machine",

author = "Ruyan Fu and Cheng, {Edwin Tai Chiu} and Ng, {Chi To} and Jinjiang Yuan",

year = "2013",

month = may,

day = "1",

doi = "10.1016/j.orl.2013.01.003",

language = "English",

volume = "41",

pages = "216--219",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan

AU - Fu, Ruyan

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

AU - Yuan, Jinjiang

PY - 2013/5/1

Y1 - 2013/5/1

N2 - We consider the online scheduling of incompatible job families on an unbounded parallel-batch machine to minimize the makespan, where jobs arrive over time and the number of job families, f, is known in advance. We provide an optimal online algorithm for the problem with a competitive ratio of 1+4f2+1-12f.

AB - We consider the online scheduling of incompatible job families on an unbounded parallel-batch machine to minimize the makespan, where jobs arrive over time and the number of job families, f, is known in advance. We provide an optimal online algorithm for the problem with a competitive ratio of 1+4f2+1-12f.

KW - Competitive ratio

KW - Incompatible job families

KW - Online scheduling

KW - Parallel-batch machine

UR - http://www.scopus.com/inward/record.url?scp=84873453341&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2013.01.003

DO - 10.1016/j.orl.2013.01.003

M3 - Journal article

SN - 0167-6377

VL - 41

SP - 216

EP - 219

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this