Research On Multi-Objective Flexible Job Shop Scheduling Algorithm For Hybrid Job Shop Line

From the national major strategic needs of industrial intelligence,the production line has changed from producing one kind of workpiece to producing multiple kinds of workpieces,which is referred to as hybrid job shop.In this production mode,different types of products have similar operations,but different specifications,properties and models leading to coupling among operations of different jobs.In order to satisfy the rapid delivery of products,scheduling systems should consider many dynamic factors,such as machine breakdown,machine switching and job insertion.Therefore,it becomes significant to comprehensively improve the rapid delivery capability and build a flexible scheduling system that meets multiple objectives,multiple constraints,dynamic adaption and fast feedback,which has become one of the frontier studies under upgrading of traditional industries.In this dissertation,flexible job shop scheduling problem(FJSP)for hybrid job shop line is used as the application scenario.Four technologies including job relation representation,static multi-objective scheduling,dynamic multi-objective scheduling and fast scheduling are studied to find the job path and assign the corresponding machines more effectively.The specific research contents and core innovations are as follows.Firstly,for the problem of high coupling among different jobs which is difficult to be fully characterized by existing modeling technologies,a multi-graph based feedforward relation model(MFRM)is built to represent complex relationships.The job relationships are divided into sequential relation,tree structure relation and cross relation.After analyzing each type of job relations in detail,a multi-graph based feedforward relation model is constructed by using the virtual process.The model not only expresses the complex constraint relation among jobs,but also avoids the repeated calculation of combined processes.Furthermore,comparing to other classical scheduling algorithms on the same dataset,the results show that MFRM could provide a fundamental mathematical constraint model for the subsequent scheduling algorithms to ensure the availability of the scheduling results.Secondly,in hybrid job shop lines,one machine can process multiple jobs at the same time and selected machines with breakdown risk leading to processing delays,a hybrid robust scheduling algorithm(HRM)based on relation grouping and remaining useful life(RUL)prediction is proposed.During the job arrangement stage,the initialization and update methods are improved to enhance the efficiency and availability of meta-heuristic algorithms.At the stage of machine selection,a roulette selection method based on the machine health rate is formed by constructing the remaining useful life prediction model.The above method may reduce the processing delay caused by the poor job arrangement and machine selection of existing static multi-objective scheduling algorithms.To verify the effectiveness,experimental comparisons with seven other classical algorithms on two kinds of datasets show that Pareto optimal solutions for both objectives can be obtained on 70% of the data,and the results are also much better than other algorithms under single-objective optimization.Thirdly,for the problem of poor dynamic scheduling adaption under uncertain events such as sudden machine failure,machine switching and urgent order insertion in hybrid job shop lines,a multi-objective scheduling algorithm is constructed by using double two phases deep Q-learning network(DTPDQN).In detail,we extract 9 general production environment features,designing 6 kinds of combined scheduling rules and 3 types of reward functions that correspond one-to-one with the optimization objectives.Where the selection of reward functions at the first stage is as the input of second stage to assist in the selection of combined scheduling rule algorithms.The selected combined scheduling rule could further complete the job arrangement and machine selection.The above method could enhance the scheduling performance compared with existing dynamic multi-objective scheduling algorithms with poor adaption.By constructing 27 sets of dynamic instances,DTPDQN improves up to 7.5%,20%,and 54% in the three objectives of total tardiness time,average machine utilization and makespan compared to the standard double deep Q-learning based method and 5 classical scheduling algorithms.Especially,the winning rate of all objectives is over 60%.At last,aiming at the problem of large solution space leading to low efficiency and easy to fall into local optimization,two distributed multi-objective flexible job shop scheduling algorithms(D-HRM and D-DTPDQN)are proposed based on the previous study.In this dissertation,the single scheduling algorithms of jobs or machines are integrated into 15 kinds of combined scheduling rules.These scheduling rules are used to optimize the initialization method of the metaheuristic algorithm and the action selection of the deep Q-learning based algorithm.Then,parallel computing units are designed to build a distributed multi-objective flexible job shop scheduling system.By conducting validation experiments on three types of datasets,the multi-objective scheduling accuracy is improved and the time overhead is reduced by over 80% compared to the above two algorithms,while the time overhead of D-DTPDQN is reduced by 72.8% compared to double deep Q-learning based method.