Minimizing Makespan For Batch Processing Machine With Non-identical Job Sizes Using Quantum-behaved Particle Swarm Optimization

Scheduling is an important and significant issue that affects the efficiency in industrial production. A proper scheduling scheme can reduce the production cycle, improve the output rate, reduce turnover time, cut down the inventory, ultimately reduce the costs, and increase the profits and customer satisfaction. Scheduling on batch processing machine (BPM) with non-identical job sizes is an important extension to the classical scheduling theory. Batch processing machines are encountered in many practical environments. For example, burn-in operations in semiconductor manufacturing, handling of cargo in port areas, burn-in operations in ceramic processing, and freight transportation. It is therefore of practical significance to study the problems of scheduling on BPM.At first, the background of scheduling problems was introduced. The problem of scheduling on BPM with non-identical job sizes, which is NP-hard, was mainly discussed. Previous related studies have been reviewed. Our main concern is different algorithms proposed to solve the BPM problems.Secondly, the Quantum-behaved Particle Swarm Optimization for Batch-scheduling (BQPSO) and its improved version (BIQPSO) were introduced. A novel coding approach was designed and the particles were sequenced using the priority value vectors. A heuristic was then combined with BQPSO so that the algorithm is capable of dealing with combinatorial optimization problems. For the inactivation and premature convergence of the particles during the iteration, a crossover and mutation operator were introduced to BIQPSO in order to improve the variety and search capability of the particles. Extensive computational experiments were implemented to compare BQPSO and BIQPSO with other algorithms previously proposed. The experimental results showed BQPSO and BIQPSO outperformed other algorithms, and BIQPSO had a better performance than BQPSO. And such improvement became more remarkable with large scale problems.Thirdly, the problem was extended to parallel batch processing machines. Compared with single batch processing machine scheduling problems, scheduling on parallel BPM was more widely used in industrial production. Based on the mathematical model established, Parallel-Quantum-behaved Particle Swarm Optimization for Batch-scheduling (P-BQPSO) and Parallel-Improved Quantum-behaved Particle Swarm Optimization for Batch-scheduling (P-BIQPSO) were designed. By means of stochastic simulation,examples are compared. The experiment showed that the proposed algorithms outperformed the others, and P-BIOPSO had a better performance than P-BQPSO.Suggestions and future research are presented in the last section.