Makespan minimization in single-machine scheduling with step-deterioration of processing times

Makespan minimization in single-machine scheduling with step-deterioration of processing times

0.00 Avg rating0 Votes
Article ID: iaor20051312
Country: United Kingdom
Volume: 55
Issue: 3
Start Page Number: 247
End Page Number: 256
Publication Date: Mar 2004
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: production
Abstract:

This paper considers a single-machine scheduling problem of minimizing the maximum completion time for a set of independent jobs. The processing time of a job is a non-linear step function of its starting time and due date. The problem is already known to be NP-hard in the literature. In this paper, we first show this problem to be NP-hard in the ordinary sense by proposing a pseudo-polynomial time dynamic programming algorithm. Then, we develop two dominance rules and a lower bound to design a branch-and-bound algorithm for deriving optimal solutions. Numerical results indicate that the proposed properties can effectively reduce the time required for exploring the solution space.

Reviews

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