Scheduling deteriorating jobs to minimize the makespan on a single machine

作者：Wu Chin Chia; Shiau Yau Ren; Lee Ling Huei; Lee Wen Chiung^*

来源：International Journal of Advanced Manufacturing Technology, 2009, 44(11-12): 1230-1236.

DOI：10.1007/s00170-008-1924-4

• Scheduling
• Single-machine
• Makespan
• Deteriorating jobs

Machine scheduling problems with deteriorating jobs have received increasing attention in recent years, mostly focusing on the linear deterioration models. However, if certain maintenance procedures fail to be completed prior to a prespecified deadline, jobs will require extra time for successful accomplishment in some situations. Therefore, this paper addresses a single-machine problem where the objective is to minimize the makespan under the piecewise linear deterioration model. A branch-and-bound algorithm and two heuristic algorithms are provided to search for the optimal solution and near-optimal solutions, respectively. Computational results are also presented to evaluate the performance of the proposed algorithms.

• 出版日期2009-10