Research On Parallel Multi-machine Batch Scheduling Problem

Problem of parallel multi-machine batch scheduling is the study of a kind ofscheduling problem with jobs into batches and multiple machines; it is a new researchdirection in the field of production scheduling, and has been applied widely in manyfields such as semiconductor production, steelmaking, the scheduling of multi-stagelock, transportation. Most of batch scheduling problem is a NP-hard problem, becausethe parallel multi-machine batch scheduling problem is more complex than theclassical scheduling problem. Thus, seeking the effective algorithm used to solve theparallel multi-machine batch scheduling problem has theoretic significance andpractical value.This paper has opened out further research, based on some references of existingproblems about parallel multi-machine batch scheduling problem. One is the fact thatmost references focus on the study of scheduling problem which have same size ofworkpiece, the study which have different size of workpiece is less. The second is thatthe objective of scheduling problem focus on more single-objective, less thanmulti-objective scheduling problem. For the problems, the main work of the paper isthe following.（1）A new hybrid algorithm, particle bee colony algorithm has been proposedbased on particle swarm optimization and artificial bee colony algorithm. The hybridalgorithm inherits the advantage of PSO about rapid convergence and strong ability oflocal search; it also has the strong development capability of ABC to jump out thelocal optimum, thus balanced the exploration and exploitation capability of algorithm.（2）The weight coefficient and learning factors of PSO are improved based onthe particle bee colony algorithm, and the improved particle bee colony algorithm isapplied to solve parallel multi-machine batch scheduling problem with the objectiveto minimize makespan. This paper increases large-scale scheduling problem and theparallel machines to validate the effectiveness of particle bee colony algorithm forsolving the scheduling problem, and the result is compared with the result of PSO andGA. The result shows that particle bee colony algorithm for solving the schedulingproblem is effective, and the effect is better than other two algorithm.（3）The multi-objective parallel multi-machine batch scheduling problem isstudied due to less researching on this kind of problem. The crossover and mutation ofgenetic algorithm and the elite strategy are introduced to the particle swarm optimization based on the success of NSGA-II algorithm for solving themulti-objective problems. Through a series of simulation experments, the improvedmulti-objective particle swarm optimization is effective to solve the multi-objectivescheduling problem, and the result is compared with the result of unimproved PSOand NSGA-II. The result shows that the Pareto solution used the improved particleswarm optimization is more close to the Pareto front, and keeps the diversity andevenness of solutions.