Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration

作者：Low Chinyao; Hsu Chou Jung; Su Chwen Tzeng

来源：Computers & Mathematics with Applications, 2008, 56(1): 257-265.

DOI：10.1016/j.camwa.2007.12.006

• simple linear deterioration
• makespan
• 0-1 integer programming
• bin packing

This article considers a single machine scheduling problem with an availability constraint under simple linear deterioration. The non-preemptive case is taken into account as well. The objective is to minimize the makespan in the system. The addressed problem is first described as a 0-1 integer programming model, and is then solved optimally. Subsequently, we prove that the addressed problem belongs to NP-hard. Thus, some heuristic algorithms based on the bin packing concepts are provided for solving the addressed problem. Computational results show that the proposed algorithm H3 performs well. In addition, a good strategy that sets the maintenance to start epoch when half the jobs have been already processed is suggested as well.

• 出版日期2008-7