Single‐machine makespan minimization scheduling with nonlinear shortening processing times

Single‐machine makespan minimization scheduling with nonlinear shortening processing times

0.00 Avg rating0 Votes
Article ID: iaor20117137
Volume: 39
Issue: 3
Start Page Number: 659
End Page Number: 663
Publication Date: Mar 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: scheduling, combinatorial optimization
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.

Reviews

Required fields are marked *. Your email address will not be published.