Single‐machine scheduling with nonlinear deterioration

Single‐machine scheduling with nonlinear deterioration

0.00 Avg rating0 Votes
Article ID: iaor2012327
Volume: 6
Issue: 1
Start Page Number: 87
End Page Number: 98
Publication Date: Jan 2012
Journal: Optimization Letters
Authors: ,
Keywords: combinatorial optimization, heuristics
Abstract:

In this paper, we consider the single‐machine scheduling problems with nonlinear deterioration. By the nonlinear deterioration effect, we mean that the processing times of jobs are nonlinear functions of their starting times. We show that even with the introduction of nonlinear deterioration to job processing times, single machine makespan minimization problem remains polynomially solvable. We also show that an optimal schedule of the total completion time minimization problem is V‐shaped with respect to job normal processing times. A heuristic algorithm utilizing the V‐shaped property is proposed, and computational experiments show that it performs effectively and efficiently in obtaining near‐optimal solutions.

Reviews

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