Article ID Journal Published Year Pages File Type
10347621 Computers & Operations Research 2012 5 Pages PDF
Abstract
In this paper, we consider the single-machine makespan minimization scheduling problem with nonlinear shortening processing times. By the nonlinear shortening processing times, we mean that the processing times of jobs are non-increasing nonlinear functions of their starting times. The computational complexity of the general problem remains an open problem, but we show that even with the introduction of nonlinear shortening processing times to job processing times, some special cases remain polynomially solvable. We also show that an optimal schedule of the general makespan minimization problem is V-shaped with respect to job normal processing times. A heuristic algorithm which utilize the V-shaped property is proposed, and computational experiments show that it is effective and efficient in obtaining near-optimal solutions.
Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, ,