The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard

Edwin Tai Chiu Cheng; Chi To Ng; J. J. Yuan

doi:10.1023/A:1024858623282

The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard

Edwin Tai Chiu Cheng, Chi To Ng, J. J. Yuan

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

21 Citations (Scopus)

Abstract

In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. While the problem was proved to be binary NP-hard in 1978, whether the problem is strongly NP-hard is a long-standing open question. We show that this problem is strongly NP-hard.

Original language	English
Pages (from-to)	483-490
Number of pages	8
Journal	Journal of Scheduling
Volume	6
Issue number	5
DOIs	https://doi.org/10.1023/A:1024858623282
Publication status	Published - 1 Sept 2003

Keywords

Batching
Due-dates
Maximum lateness
Multi-operation jobs
Scheduling

ASJC Scopus subject areas

Industrial and Manufacturing Engineering
Management Science and Operations Research

More information

10.1023/A:1024858623282

http://hdl.handle.net/10397/1069

Cite this

@article{ea42ebf73b784b4e9334319c54e2fb83,

title = "The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard",

abstract = "In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. While the problem was proved to be binary NP-hard in 1978, whether the problem is strongly NP-hard is a long-standing open question. We show that this problem is strongly NP-hard.",

keywords = "Batching, Due-dates, Maximum lateness, Multi-operation jobs, Scheduling",

author = "Cheng, {Edwin Tai Chiu} and Ng, {Chi To} and Yuan, {J. J.}",

year = "2003",

month = sep,

day = "1",

doi = "10.1023/A:1024858623282",

language = "English",

volume = "6",

pages = "483--490",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer New York",

number = "5",

}

TY - JOUR

T1 - The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

AU - Yuan, J. J.

PY - 2003/9/1

Y1 - 2003/9/1

N2 - In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. While the problem was proved to be binary NP-hard in 1978, whether the problem is strongly NP-hard is a long-standing open question. We show that this problem is strongly NP-hard.

AB - In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. While the problem was proved to be binary NP-hard in 1978, whether the problem is strongly NP-hard is a long-standing open question. We show that this problem is strongly NP-hard.

KW - Batching

KW - Due-dates

KW - Maximum lateness

KW - Multi-operation jobs

KW - Scheduling

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

U2 - 10.1023/A:1024858623282

DO - 10.1023/A:1024858623282

M3 - Journal article

SN - 1094-6136

VL - 6

SP - 483

EP - 490

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 5

ER -

The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this