Single machine scheduling with step-deteriorating processing times

Research output: Journal article publicationJournal articleAcademic researchpeer-review

68 Citations (Scopus)

Abstract

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
Volume134
Issue number3
DOIs
Publication statusPublished - 1 Nov 2001

Keywords

  • 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

Cite this