The complexity of single machine scheduling with two distinct deadlines and identical decreasing rates of processing times

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

The makespan problem on a single machine for a set of tasks with two distinct deadlines and identical decreasing rates of processing times is considered in this paper. Ho et al. [1] have proposed a model of a task system in which the processing time of a task decreases with its starting time. When the decreasing rate is identical, the computational complexity of the makespan problem with two distinct deadlines is posed as an open problem. In this paper we show that the problem is NP-complete. It follows that both the corresponding flow time problem and maximum lateness problem are also NP-complete.
Original languageEnglish
Pages (from-to)95-100
Number of pages6
JournalComputers and Mathematics with Applications
Volume35
Issue number12
DOIs
Publication statusPublished - 1 Jan 1998

Keywords

  • Computational complexity
  • Scheduling
  • Sequencing
  • Time-dependence

ASJC Scopus subject areas

  • Modelling and Simulation
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this