Scheduling jobs with release dates on parallel batch processing machines

L. L. Liu; Chi To Ng; Edwin Tai Chiu Cheng

doi:10.1016/j.dam.2008.12.012

Scheduling jobs with release dates on parallel batch processing machines

L. L. Liu, Chi To Ng, Edwin Tai Chiu Cheng

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

14 Citations (Scopus)

Abstract

In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.

Original language	English
Pages (from-to)	1825-1830
Number of pages	6
Journal	Discrete Applied Mathematics
Volume	157
Issue number	8
DOIs	https://doi.org/10.1016/j.dam.2008.12.012
Publication status	Published - 28 Apr 2009

Keywords

Computational Complexity
Parallel batch processing machines
PTAS
Release dates
Scheduling

ASJC Scopus subject areas

Applied Mathematics
Discrete Mathematics and Combinatorics

More information

10.1016/j.dam.2008.12.012

Cite this

@article{cf8cdda8053f4518be22bbdaadb9dbd0,

title = "Scheduling jobs with release dates on parallel batch processing machines",

abstract = "In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.",

keywords = "Computational Complexity, Parallel batch processing machines, PTAS, Release dates, Scheduling",

author = "Liu, {L. L.} and Ng, {Chi To} and Cheng, {Edwin Tai Chiu}",

year = "2009",

month = apr,

day = "28",

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

language = "English",

volume = "157",

pages = "1825--1830",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "8",

}

TY - JOUR

T1 - Scheduling jobs with release dates on parallel batch processing machines

AU - Liu, L. L.

AU - Ng, Chi To

AU - Cheng, Edwin Tai Chiu

PY - 2009/4/28

Y1 - 2009/4/28

N2 - In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.

AB - In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.

KW - Computational Complexity

KW - Parallel batch processing machines

KW - PTAS

KW - Release dates

KW - Scheduling

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

U2 - 10.1016/j.dam.2008.12.012

DO - 10.1016/j.dam.2008.12.012

M3 - Journal article

SN - 0166-218X

VL - 157

SP - 1825

EP - 1830

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 8

ER -

Scheduling jobs with release dates on parallel batch processing machines

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this