The time dependent machine makespan problem is strongly NP-complete

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

The computational complexity of the problem of scheduling a set of start-time dependent tasks with deadlines and identical decreasing rates of processing times on a single machine to minimize the makespan is open. In this paper we show that the problem is strongly NP-complete by a reduction from 3-Partition. Scope and purpose There has been increasing interest in scheduling models where the job processing times are a function of their starting times. There are many practical scheduling problems that can be modeled in this way. We study one such model where the job processing times decrease linearly with their starting times. The jobs have the same processing time decreasing rates but each job has an individual deadline which cannot be exceeded. The problem is to find a feasible schedule satisfying the deadline constraints that minimizes the makespan. This is an open problem in the literature and we show that it is strongly NP-complete. Thus, future research on this model should be focussed on the design of effective heuristics.
Original languageEnglish
Pages (from-to)749-754
Number of pages6
JournalComputers and Operations Research
Volume26
Issue number8
DOIs
Publication statusPublished - 1 Jul 1999

Keywords

  • Computational complexity
  • Scheduling
  • Sequencing
  • Time dependence

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this