๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by C.T. Ng; T.C.E. Cheng; A. Bachman; A. Janiak

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
84 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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(n log n) 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.

๐Ÿ“œ SIMILAR VOLUMES

Scheduling with tool changes to minimize
Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance
โœ M. Selim Akturk; Jay B. Ghosh; Evrim D. Gunes ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 114 KB

## Abstract The machine scheduling literature does not consider the issue of tool change. The parallel literature on tool management addresses this issue but assumes that the change is due only to part mix. In practice, however, a tool change is caused most frequently by tool wear. That is why we c

Strong NP-hardness of the single machine
Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem
โœ C.T. Ng; T.C.E. Cheng; J.J. Yuan ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 58 KB

We consider the single machine multi-operation jobs total completion time scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes w