Improved DE search for competing groups scheduling with deterioration effects

Abstract

This paper investigates a three-competing group scheduling problem on serial-batching machines considering the setup time of groups and batches, as well as the job-dependent deteriorating effect, where the setup time of groups and batches depends on their own corresponding start time and deterioration rate, and the jobs’ actual processing time depends on their starting time and deterioration rate. In this problem, the jobs in three groups are processed competitively, and the jobs belonging to the same group are processed together on a machine, meanwhile, the jobs from each group are divided into batches. The objective is to minimize the makespan of one group with deterioration effect under the constraint of satisfying the threshold value of another group. Some key structural properties are proposed under the relevant demonstration, and a decision flow chart of scheduling rules is constructed based on these structural properties. Then, an effective improved differential evolution (DE) search algorithm combining the shaking operation from variable neighborhood search is developed to solve the studied scheduling problem. Computational experiments are conducted to evaluate the performance of proposed improved DE algorithm and some other well-known algorithms. The experimental results show that the proposed algorithm is more effective and stable than compared algorithms.