On scheduling unbounded batch processing machine(s)

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

doi:10.1016/j.cie.2010.02.003

On scheduling unbounded batch processing machine(s)

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

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

2 Citations (Scopus)

Abstract

The computational complexity of scheduling jobs with released dates on an unbounded batch processing machine to minimize total completion time and on parallel unbounded batch processing machines to minimize total weighted completion time remains open. In this note we show that the first problem is NP-hard with respect to id-encoding, and the second one is strongly NP-hard.

Original language	English
Pages (from-to)	814-817
Number of pages	4
Journal	Computers and Industrial Engineering
Volume	58
Issue number	4
DOIs	https://doi.org/10.1016/j.cie.2010.02.003
Publication status	Published - 1 May 2010

Keywords

Batch processing
Computational complexity
Scheduling

ASJC Scopus subject areas

General Computer Science
General Engineering

More information

10.1016/j.cie.2010.02.003

Cite this

@article{2e6b8e07593c4648be5b54eec0a92f36,

title = "On scheduling unbounded batch processing machine(s)",

abstract = "The computational complexity of scheduling jobs with released dates on an unbounded batch processing machine to minimize total completion time and on parallel unbounded batch processing machines to minimize total weighted completion time remains open. In this note we show that the first problem is NP-hard with respect to id-encoding, and the second one is strongly NP-hard.",

keywords = "Batch processing, Computational complexity, Scheduling",

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

year = "2010",

month = may,

day = "1",

doi = "10.1016/j.cie.2010.02.003",

language = "English",

volume = "58",

pages = "814--817",

journal = "Computers and Industrial Engineering",

issn = "0360-8352",

publisher = "Elsevier Ltd",

number = "4",

}

TY - JOUR

T1 - On scheduling unbounded batch processing machine(s)

AU - Liu, L. L.

AU - Ng, Chi To

AU - Cheng, Edwin Tai Chiu

PY - 2010/5/1

Y1 - 2010/5/1

N2 - The computational complexity of scheduling jobs with released dates on an unbounded batch processing machine to minimize total completion time and on parallel unbounded batch processing machines to minimize total weighted completion time remains open. In this note we show that the first problem is NP-hard with respect to id-encoding, and the second one is strongly NP-hard.

AB - The computational complexity of scheduling jobs with released dates on an unbounded batch processing machine to minimize total completion time and on parallel unbounded batch processing machines to minimize total weighted completion time remains open. In this note we show that the first problem is NP-hard with respect to id-encoding, and the second one is strongly NP-hard.

KW - Batch processing

KW - Computational complexity

KW - Scheduling

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

U2 - 10.1016/j.cie.2010.02.003

DO - 10.1016/j.cie.2010.02.003

M3 - Journal article

SN - 0360-8352

VL - 58

SP - 814

EP - 817

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

IS - 4

ER -

On scheduling unbounded batch processing machine(s)

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this