Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)

Abstract

We consider the single machine multi-operation jobs total completion time scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes when all of its operations have been processed. The objective is to minimize the sum of the job completion times. In the literature, the computational complexity of this problem is posed as open. We show that the problem is strongly NP-hard even when the set-up times are common and the processing time of each operation is 0 or 1.
Original languageEnglish
Pages (from-to)187-191
Number of pages5
JournalInformation Processing Letters
Volume82
Issue number4
DOIs
Publication statusPublished - 31 May 2002

Keywords

  • Scheduling
  • Single machine multi-operation jobs

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem'. Together they form a unique fingerprint.

Cite this