Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine

Research output: Journal article publicationJournal articleAcademic researchpeer-review

32 Citations (Scopus)


In this paper, we study the feasibility problem of scheduling a set of start time dependent tasks on a single machine with deadlines, processing rates and identical initial processing times. First, we show that the cases with arbitrary deadlines are strongly NP-complete. Second, we show that the cases with two distinct deadlines are NP-complete in the ordinary sense. Finally, we give an optimal polynomial algorithm for the makespan problem with two distinct processing rates. We solve a series of open problems in the literature and give a sharp boundary delineating the complexity of the problems.
Original languageEnglish
Pages (from-to)51-62
Number of pages12
JournalComputers and Operations Research
Issue number1
Publication statusPublished - 1 Jan 2003


  • Computational complexity
  • Sequencing
  • Time dependence scheduling

ASJC Scopus subject areas

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

Cite this