An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

Ji Tian; Edwin Tai Chiu Cheng; Chi To Ng; Jinjiang Yuan

doi:10.1016/j.dam.2011.12.002

An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

Ji Tian, Edwin Tai Chiu Cheng, Chi To Ng, Jinjiang Yuan

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

16 Citations (Scopus)

Abstract

We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio 22-1≈1.828, which improves on a 2-competitive on-line algorithm for this problem in the literature.

Original language	English
Pages (from-to)	1191-1210
Number of pages	20
Journal	Discrete Applied Mathematics
Volume	160
Issue number	7-8
DOIs	https://doi.org/10.1016/j.dam.2011.12.002
Publication status	Published - 1 May 2012

Keywords

Competitive ratio
Delivery times
On-line scheduling
Parallel-batch machine

ASJC Scopus subject areas

Applied Mathematics
Discrete Mathematics and Combinatorics

More information

10.1016/j.dam.2011.12.002

Cite this

@article{f0a18998a8ee415ba1107f8e0641245e,

title = "An improved on-line algorithm for single parallel-batch machine scheduling with delivery times",

abstract = "We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio 22-1≈1.828, which improves on a 2-competitive on-line algorithm for this problem in the literature.",

keywords = "Competitive ratio, Delivery times, On-line scheduling, Parallel-batch machine",

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

year = "2012",

month = may,

day = "1",

doi = "10.1016/j.dam.2011.12.002",

language = "English",

volume = "160",

pages = "1191--1210",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "7-8",

}

TY - JOUR

T1 - An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

AU - Tian, Ji

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

AU - Yuan, Jinjiang

PY - 2012/5/1

Y1 - 2012/5/1

N2 - We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio 22-1≈1.828, which improves on a 2-competitive on-line algorithm for this problem in the literature.

AB - We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio 22-1≈1.828, which improves on a 2-competitive on-line algorithm for this problem in the literature.

KW - Competitive ratio

KW - Delivery times

KW - On-line scheduling

KW - Parallel-batch machine

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

U2 - 10.1016/j.dam.2011.12.002

DO - 10.1016/j.dam.2011.12.002

M3 - Journal article

SN - 0166-218X

VL - 160

SP - 1191

EP - 1210

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 7-8

ER -

An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this