Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan

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

doi:10.1016/j.ipl.2010.04.008

Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan

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

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

8 Citations (Scopus)

Abstract

We study online scheduling on two unbounded parallel-batching machines with limited restarts to minimize the makespan. In this system jobs arrive over time and a batch can be restarted if and only if all the jobs in it have never been restarted. To tackle this difficult problem, we make the second-restart assumption whereby we can only interrupt a running batch B at time t if both machines are busy at time t and batch B has a later starting time than the other running batch. For this case, we provide a best online algorithm with a competitive ratio ?3+12 ≈ 1.366. For the general problem, we show that no online algorithms can have a competitive ratio less than 1.298, leaving a gap from 1.298 to 1.366.

Original language	English
Pages (from-to)	444-450
Number of pages	7
Journal	Information Processing Letters
Volume	110
Issue number	11
DOIs	https://doi.org/10.1016/j.ipl.2010.04.008
Publication status	Published - 16 May 2010

Keywords

Analysis of algorithm
Competitive ratio
Limited restart
Online scheduling
Parallel-batching machines

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

More information

10.1016/j.ipl.2010.04.008

Cite this

@article{964fe36599514bbf9ee70b459e6c1202,

title = "Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan",

abstract = "We study online scheduling on two unbounded parallel-batching machines with limited restarts to minimize the makespan. In this system jobs arrive over time and a batch can be restarted if and only if all the jobs in it have never been restarted. To tackle this difficult problem, we make the second-restart assumption whereby we can only interrupt a running batch B at time t if both machines are busy at time t and batch B has a later starting time than the other running batch. For this case, we provide a best online algorithm with a competitive ratio ?3+12 ≈ 1.366. For the general problem, we show that no online algorithms can have a competitive ratio less than 1.298, leaving a gap from 1.298 to 1.366.",

keywords = "Analysis of algorithm, Competitive ratio, Limited restart, Online scheduling, Parallel-batching machines",

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

year = "2010",

month = may,

day = "16",

doi = "10.1016/j.ipl.2010.04.008",

language = "English",

volume = "110",

pages = "444--450",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "11",

}

TY - JOUR

T1 - Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan

AU - Fu, Ruyan

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

AU - Yuan, Jinjiang

PY - 2010/5/16

Y1 - 2010/5/16

N2 - We study online scheduling on two unbounded parallel-batching machines with limited restarts to minimize the makespan. In this system jobs arrive over time and a batch can be restarted if and only if all the jobs in it have never been restarted. To tackle this difficult problem, we make the second-restart assumption whereby we can only interrupt a running batch B at time t if both machines are busy at time t and batch B has a later starting time than the other running batch. For this case, we provide a best online algorithm with a competitive ratio ?3+12 ≈ 1.366. For the general problem, we show that no online algorithms can have a competitive ratio less than 1.298, leaving a gap from 1.298 to 1.366.

AB - We study online scheduling on two unbounded parallel-batching machines with limited restarts to minimize the makespan. In this system jobs arrive over time and a batch can be restarted if and only if all the jobs in it have never been restarted. To tackle this difficult problem, we make the second-restart assumption whereby we can only interrupt a running batch B at time t if both machines are busy at time t and batch B has a later starting time than the other running batch. For this case, we provide a best online algorithm with a competitive ratio ?3+12 ≈ 1.366. For the general problem, we show that no online algorithms can have a competitive ratio less than 1.298, leaving a gap from 1.298 to 1.366.

KW - Analysis of algorithm

KW - Competitive ratio

KW - Limited restart

KW - Online scheduling

KW - Parallel-batching machines

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

U2 - 10.1016/j.ipl.2010.04.008

DO - 10.1016/j.ipl.2010.04.008

M3 - Journal article

SN - 0020-0190

VL - 110

SP - 444

EP - 450

JO - Information Processing Letters

JF - Information Processing Letters

IS - 11

ER -

Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this