An Optimization Method for a Single Machine Multi-family Scheduling Problem with Qualification Run Constraints

The qualification run (qual-run) as a technique to avoid possible quality problems of products inevitably leads to much longer cycle time. To effectively balance the trade-off between the qual-run and setup times, a scheduling model of a single machine with multiple families was developed and an adaptive differential evolution algorithm based on catastrophe with depth neighborhood search was applied to resolve the problem. First, a scheduling problem domain was described, and a mathematical programming model was set up with an objective of minimizing makespan. Further, several theorems were developed to construct feasible solutions. On the basis of differential evolution, the depth neighborhood search operator was adopted to search a wide range of solutions. In addition, the adaptive process and catastrophe theory were combined to improve the performance of the algorithm. Finally, simulation experiments were carried out and the results indicated that the proposed algorithm was effective and efficient.