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

Research output: Journal article publicationJournal articleAcademic researchpeer-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 languageEnglish
Pages (from-to)483-490
Number of pages8
JournalJournal of Scheduling
Volume6
Issue number5
DOIs
Publication statusPublished - 1 Sep 2003

Keywords

  • Batching
  • Due-dates
  • Maximum lateness
  • Multi-operation jobs
  • Scheduling

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Management Science and Operations Research

Cite this