A new single machine scheduling problem with setup time, job deterioration and maintenance costs

摘要

In this paper, a single machine scheduling problem with sequence-dependent setup times is studied so as to minimize the total costs of tardiness and earliness of all jobs and costs regarding to machine processing and maintenance activities. Furthermore, processing times of jobs are determined according to a deterioration function. Maintenance activities are also planned in order to reduce processing times of jobs. Hence, a new mathematical model is presented, in which the number and the sequence of maintenance activities are considered as decision variables. Because the problem belongs to the class of NP-Hard ones, a new hybrid simulated annealing (HSA) algorithm is proposed to obtain an optimal solution in a reasonable run time. The proposed HSA utilizes from local heuristic search to improve the chance of obtaining better optimal solutions. Computational experiences indicate that the hybrid algorithm has the superior performance in contrast to that of previous studies.