A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

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

doi:10.1007/s10951-010-0172-2

A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

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

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

17 Citations (Scopus)

Abstract

We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5-√5)/2.We give an online algorithm for the considered problem with a competitive ratio (5 -√5)/2 ≈ 1.382.

Original language	English
Pages (from-to)	361-369
Number of pages	9
Journal	Journal of Scheduling
Volume	14
Issue number	4
DOIs	https://doi.org/10.1007/s10951-010-0172-2
Publication status	Published - 1 Aug 2011

Keywords

Competitive ratio
Online algorithm
Parallel-batch scheduling
Restart

ASJC Scopus subject areas

Software
Artificial Intelligence
General Engineering
Management Science and Operations Research

More information

10.1007/s10951-010-0172-2

Cite this

@article{a06edd2121cf439a8d88a1860b806766,

title = "A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan",

abstract = "We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5-√5)/2.We give an online algorithm for the considered problem with a competitive ratio (5 -√5)/2 ≈ 1.382.",

keywords = "Competitive ratio, Online algorithm, Parallel-batch scheduling, Restart",

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

year = "2011",

month = aug,

day = "1",

doi = "10.1007/s10951-010-0172-2",

language = "English",

volume = "14",

pages = "361--369",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

AU - Yuan, Jinjiang

AU - Fu, Ruyan

AU - Ng, Chi To

AU - Cheng, Edwin Tai Chiu

PY - 2011/8/1

Y1 - 2011/8/1

N2 - We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5-√5)/2.We give an online algorithm for the considered problem with a competitive ratio (5 -√5)/2 ≈ 1.382.

AB - We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5-√5)/2.We give an online algorithm for the considered problem with a competitive ratio (5 -√5)/2 ≈ 1.382.

KW - Competitive ratio

KW - Online algorithm

KW - Parallel-batch scheduling

KW - Restart

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

U2 - 10.1007/s10951-010-0172-2

DO - 10.1007/s10951-010-0172-2

M3 - Journal article

SN - 1094-6136

VL - 14

SP - 361

EP - 369

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 4

ER -

A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this