Optimization Study For Job Shop Scheduling Problem Considering Material Handling Time

Most of the traditional Job Shop Scheduling Problems only involve the scheduling of the workstations without considering the material handling time.However,in the practical processing of the production,the job shop scheduling is generally accompanied by the scheduling of the material handling equipment,and the two scheduling problems coordinate with each other,thus arranging their scheduling reasonably to minimize the makespan can effectively improve the productivity of the workshop.As the main material handling equipment in the large-scale equipment manufacturing and assembly workshop,cranes have some unique properties which need further study and exploration.This paper mainly aims to study the Job Shop Scheduling Problem considering the influence of the material handling time,and through the analysis of the transfer process of materials between the workstations,the paper explores how to generate efficient crane scheduling strategies.Taking the minimization of makespan as the important target,the programming models of the Job Shop Scheduling Problem under the influence of the material handling time are constructed by considering the constraints of the sequence constraints of crane handling task and workstation processing task and the own process constraints of the workpiece,then some appropriate heuristic algorithms are sought to solve the problem,so as to obtain a better scheduling scheme and achieve the efficient operation of the whole operation process.This paper includes the following four parts:(1)The study background and practical meaning of this paper is introduced briefly,and the study status of the Job Shop Scheduling Problem and Crane Scheduling Problem at home and abroad are summarized comprehensively,which provides a technical reference for the modeling and the optimization strategy design of the problems considered in this paper.(2)The Job Shop Scheduling Problem considering crane handling process is analyzed.Starting from a single crane problem,the goal is to minimize the makespan,and the corresponding mixed integer programming model is established,then an improved genetic algorithm based on precedence operation crossover operator and insert mutation operator is designed to solve the problem,the initial population is generated by a heuristic method combining the Most Work Remaining rule,the Shortest Processing Time rule and Random rule,and local neighborhood search is added to improve the quality of solution,finally,the effectiveness of the algorithm is verified by the computational experiment.(3)For the Job Shop Scheduling Problem considering multi-crane handling operation,the problems of simultaneous operation conflict and the minimum crane travel time span in multi-crane operation process are analyzed,then the interference constraints and safety margins constraints are added to the mathematical programming model to avoid conflicts,finally,a simple example is given to show the solution of the model.(4)On the basis of the previous model for the Job Shop Scheduling Problem considering multi-crane handling operation,based on the Fix-and-optimize algorithm framework,two heuristic methods are designed by using the release time of the handling task and the solution of the degenerate Job Shop Scheduling Problem to obtain the initial feasible solution,and eleven decomposition operators are designed according to the characteristics of the problem,then the problem is solved by combining the standard solver,and the experimental results show that the algorithm achieves good results both in time and solution quality.