Technical note: A note on the complexity of family scheduling to minimize the number of late jobs

Edwin Tai Chiu Cheng; Zhaohui Liu; Yakov M. Shafransky

doi:10.1002/jos.77

Technical note: A note on the complexity of family scheduling to minimize the number of late jobs

Edwin Tai Chiu Cheng, Zhaohui Liu, Yakov M. Shafransky

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

2 Citations (Scopus)

Abstract

The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and processing times are one unit.

Original language	English
Pages (from-to)	225-229
Number of pages	5
Journal	Journal of Scheduling
Volume	4
Issue number	4
DOIs	https://doi.org/10.1002/jos.77
Publication status	Published - 1 Dec 2001

Keywords

Family scheduling
Number of late jobs
Strong NP-hardness

ASJC Scopus subject areas

Software
General Engineering
Management Science and Operations Research
Artificial Intelligence

More information

10.1002/jos.77

Cite this

@article{da7b36ad224442339088d81bb17fd9eb,

title = "Technical note: A note on the complexity of family scheduling to minimize the number of late jobs",

abstract = "The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and processing times are one unit.",

keywords = "Family scheduling, Number of late jobs, Strong NP-hardness",

author = "Cheng, {Edwin Tai Chiu} and Zhaohui Liu and Shafransky, {Yakov M.}",

year = "2001",

month = dec,

day = "1",

doi = "10.1002/jos.77",

language = "English",

volume = "4",

pages = "225--229",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Technical note: A note on the complexity of family scheduling to minimize the number of late jobs

AU - Cheng, Edwin Tai Chiu

AU - Liu, Zhaohui

AU - Shafransky, Yakov M.

PY - 2001/12/1

Y1 - 2001/12/1

N2 - The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and processing times are one unit.

AB - The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and processing times are one unit.

KW - Family scheduling

KW - Number of late jobs

KW - Strong NP-hardness

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

U2 - 10.1002/jos.77

DO - 10.1002/jos.77

M3 - Journal article

SN - 1094-6136

VL - 4

SP - 225

EP - 229

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 4

ER -

Technical note: A note on the complexity of family scheduling to minimize the number of late jobs

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this