Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs

Abstract

In many real situations, it is found that if certain maintenance procedures fail to be completed prior to a pre-specified deterioration date, then the jobs will require extra time for successful completion. In this paper, a single-machine total completion time problem with step-deteriorating jobs is considered. A branch-and-bound method incorporated with several dominance properties and a lower bound is developed to derive the optimal solution for this problem. In addition, a weight-combination search algorithm is proposed to search for a near-optimal solution. Computational results indicate that the branch-and-bound algorithm can solve most of the problems with up to 24 jobs in a reasonable amount of time. Moreover, the proposed heuristic algorithm is accurate with mean deviations from the optimum value of less than 0.3%.

Keywords:

• scheduling
• single-machine
• step-deteriorating jobs
• total completion time

Acknowledgements

The authors are grateful to the editor and two anonymous referees whose constructive comments have led to a substantial improvement in the presentation of the paper.