Application And Research On ACO Algorithm For Batch Scheduling On Non-identical Parallel Machines

Scheduling problems are widely applied in real production environments.With the rapid development of national manufacturing industry recently,the production environment of manufacturing industry tends to be diversified and complicated.In this thesis,a batching scheduling problem on parallel machines with non-identical capacities,different weights,unequal processing time and sizes of jobs.The batching scheduling problem(BSP)on parallel machines with non-identical capacities is extended from the BSP on parallel machines with identical capacity.However,the methods solving the BSPs on parallel machines with identical capacity cannot be applied to the BSPs on parallel machines with non-identical capacities,directly.Therefore,it is vital important to design effective algorithms to address the NP-hard BSP on machines with non-identical capacities.A new ant colony algorithm is proposed to solve the studied problem.Firstly,two pheromone cooperated with two different heuristic information is used to guide the search of ants,jointly.Which uses two different candidate list to reduce the search space of the ant colony,and introduces optimizing solution by adjusting the job position of local optimization strategy.Two candidate lists are adopted to narrow the search space of ants hierarchically.Secondly,the local optimization strategy of modulating job locations is further used to improve the solution quality.Finally,the performance of the proposed algorithm is verified through simulation experiments.Besides,the proposed algorithm is compared with three other algorithms.The experimental results show that the solution quality obtained by the proposed double-pheromone ant colony optimization algorithm(BPACO)is better than those of the other compared algorithms.Moreover,with the increase of job numbers,the advantages of BPACO becomes more apparent.Furthermore,the experimental results of BPACO compared with the ant colony optimization algorithm with single pheromone demonstrates that the proposed algorithm has obvious superiority in solving the studied problem.