Research on Multi-Objective Scheduling Algorithm of Job Shop Considering Limited Storage and Transportation Capacity

Abstract

As with the continuous improvement of the workshop automation rate and the importance in energy consumption, more and more enterprises not only need to make scheduling decision on production equipment, but also need to consider whether the scheduling of transportation equipment supports scheduling decisions on workshop production. At the same time, because both workshop production scheduling decision and transportation scheduling decision are NP-hard problems, it is necessary to design an efficient algorithm to improve productivity of the workshop. In order to solve this problem, firstly, based on the analysis of the problem structure, production environment and optimization objectives, a “manufacturing-transportation” multi-objective joint scheduling optimization mathematical model is established. By converting the energy consumption into the total transportation time objective of the transportation equipment, both total transportation time and makespan are taken as the optimization objectives. Secondly, based on the design idea of memetic algorithm (MA), non-dominated sorting genetic algorithm-II(NSGA-II) is employed as the basis framework of our new developed algorithm. An effective discrete encoding scheme of MO-MA, a new initialization method for initial population and a neighborhood search mechanism based on critical path are incorporated into our new proposed algorithm. Then the parameter design of the algorithm is completed through variance analysis. Finally, the proposed algorithm is compared and analyzed with other algorithms in the dimension of hypervolume and Set Coverage (SC), and advantages of the algorithm in solving this problem are verified.

Keywords

• Job shop
• multi-objective optimization
• manufacturing-transportation
• joint scheduling
• memetic algorithm