Three scheduling problems with deteriorating jobs to minimize the total completion time

Chi To Ng, Edwin Tai Chiu Cheng, A. Bachman, A. Janiak

Research output: Journal article publicationJournal articleAcademic researchpeer-review

82 Citations (Scopus)

Abstract

In this paper, three scheduling problems with deteriorating jobs to minimize the total completion time on a single machine are investigated. By a deteriorating job, we mean that the processing time of the job is a function of its execution start time. The three problems correspond to three different decreasing linear functions, whose increasing counterparts have been studied in the literature. Some basic properties of the three problems are proved. Based on these properties, two of the problems are solved in O(nlogn) time, where n is the number of jobs. A pseudopolynomial time algorithm is constructed to solve the third problem using dynamic programming. Finally, a comparison between the problems with job processing times being decreasing and increasing linear functions of their start times is presented, which shows that the decreasing and increasing linear models of job processing times seem to be closely related to each other.
Original languageEnglish
Pages (from-to)327-333
Number of pages7
JournalInformation Processing Letters
Volume81
Issue number6
DOIs
Publication statusPublished - 31 Mar 2002

Keywords

  • Algorithms
  • Dynamic programming
  • Single machine scheduling
  • Start time dependent processing times
  • Total completion time

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this