Article ID Journal Published Year Pages File Type
474060 Computers & Operations Research 2008 10 Pages PDF
Abstract

This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series–parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, , ,