A Study Of An Improved Discrete Particle Swarm Optimization Algorithm For A Single Batch-processing Machine With Non-identical Job Sizes

Scheduling problem is one of the most important embranchment of combinatorial optimization problems. In practical applications, production scheduling plays a key role in the manufacturing systems of modern enterprises and the scheduling technologies are improved continually to satisfy the fast-changing circumstance.Begin with computational intelligence, computational complexity of algorithm and NP problem are introduced first. Coming with production scheduling problem, which is closed to the researches mentioned above. To discriminate modern scheduling from classical scheduling, we indicate four basic assumptions. One of the assumptions is that only one job could be processed on a machine at the same time. If this assumption is broken, in other words, more jobs could be processed on a machine at the same time, it will be a batch scheduling problem. Moreover, if the jobs with different sizes is allowed in batch scheduling, it will be extended to batch scheduling problem with non-identical job sizes, which is named two-dimension scheduling problem in our work. This kind of problem is more complicated than classical scheduling problem and classical batch scheduling problem while it is more closer to the requirements of manufacture environment than the formers. Therefore, two-dimension scheduling problem research has important significance in theory and economy.In addition, the origin and improvement of particle swarm optimization algorithm are introduced. We discuss the advantages or disadvantages of this algorithm. Based on the research of elders, we redesign a discrete particle swarm optimization algorithm that suitable for scheduling jobs with non-identical sizes on a single batch processing machine.After the steps above, we set the factors by elders research and our data, then compare it with simulation annealing and gene algorithm. Computational results show that it significantly outperform other algorithms addressed in literature. It means that it is more effective and efficient method for solving scheduling problems to minimize makespan on a single batch processing machine with non-identical job sizes.Finally, review the overall works and gives some research proposals.