A Mathematical Model and a Branch and Bound Algorithm for the Single Machine Scheduling Problem Under Linear Deterioration and Release Times

In this paper, the single machine scheduling problem with linear deteriorating jobs under release times is considered where the objective is to minimize the number of tardy jobs. The problem is proved NP-hard according to the literature review. At first, a mathematical model is presented to the problem and a Branch and Bound algorithm with considering dominance rules and lower bounds is supposed to solve the problem optimally. Computational results are presented in four parts to evaluate the performance of the proposed algorithm and the effect of related parameters on the algorithm. According to the variance analysis test, it was found that the efficiency of the branch and bound algorithm is high so that it is able to solve the most problems with job size 30 within a reasonable time and the average percentage of entire fathomed nodes in all the problems is at least 85.61 percentage. It was also shown the problems with larger λ and smaller deterioration rates are difficult and the average solution time of the algorithm is high for them. On the other hand, if the due date of the jobs was big or small, the problem will be simple and the solution time is less than the problems with medium due dates.