Single machine scheduling with step-deteriorating processing times

Research output: Journal article publicationJournal articleAcademic researchpeer-review

74 Citations (Scopus)


We study in this paper a scheduling model in which each task has a normal processing time which deteriorates as a step function if its starting time is beyond a given deteriorating date. We focus on problems with identical task deteriorating dates. We show that the flow time problem is NP-complete and suggest a pseudo-polynomial algorithm for the makespan problem. We also introduce a general method of solution, which facilitates the identification of solvable cases for some related problems. Finally, we provide a counter-example that invalidates the conjecture of optimality of a switching algorithm reported in the literature. Thus, we solve several unexplored or open problems and obtain a sharp boundary delineating the complexity of the considered problems.
Original languageEnglish
Pages (from-to)623-630
Number of pages8
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 1 Nov 2001


  • Computational complexity
  • Scheduling
  • Sequencing
  • Step-deterioration

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation


Dive into the research topics of 'Single machine scheduling with step-deteriorating processing times'. Together they form a unique fingerprint.

Cite this