Algorithms for scheduling problem with different deterioration jobs under depending on waiting times

In this paper, a single machine scheduling problem with deterioration jobs is investigated. It focuses on considering a new deterioration model and different deterioration rates for minimizing the makespan. Firstly, a mixed integer programming model for the scheduling problem is presented. Secondly, according to characteristics of the problem, dominance properties and lower bounds are proposed and integrated into the Branch and Bound algorithm (B&B). Thirdly, for solving a large-scale problem, the heuristic algorithm is proposed. The numerical experiments show that when the size of the problem is small, the B&B algorithm can obtain the optimal solutions in a reasonable time. ILOG CPLEX can also obtain the optimal solutions of the problem when the size of the problem is medium. A heuristic algorithm can obtain good near-optimal solutions in no more than 1s. The results of numerical experiments show that model, B&B and the heuristic algorithm are effective.