Scheduling deteriorating jobs on a single machine with release times

• DOI: 10.1016/j.cie.2007.08.006
• Publication Date: 2007-09-04T21:07:38Z
• Authors: Wen-Chiung Lee; Chin-Chia Wu; Yu-Hsiang Chung
• Keywords: Branch and bound; Single-machine scheduling

This paper investigates a single-machine deteriorating job scheduling problem with job release times where its objective is to minimize the makespan. The problem is known to be NP-hard. Therefore, a branch-and-bound algorithm incorporating with several dominance properties and lower bounds is proposed to derive the optimal solution for the problem. In addition, easy-implemented heuristic algorithms are also provided to obtain the near-optimal solution. The computational experiments indicate that the branch-and-bound algorithm can solve most of the medium-job-sized problems within a reasonable time, and the heuristic is quite accurate with an average error percentage of less than 0.3%.