Research On Job Shop Scheduling Problem Based On Two New Meta-heuristic Algorithms

Job shop scheduling problem(JSP) is a very famous workshop scheduling problem in the manufacturing area, and also one of the hardest combinatorial optimization problem. It can be expressed as follows. Each job in the workshop has a given processing route, and the using order of machine and processing time are known. It aims at solving the sequencing problem of each job on machines to achieve the optimal expected production performance. The development process is also the one in which researchers understand the nature of the problem, explore new algorithms and improve the existing algorithms. By considering the difficulty of solving the problem, meta-heuristic algorithms provide a kind of new idea and method for solving the workshop scheduling problem and have acquired extensive attention and interest of researchers at home and abroad. Two different new meta-heuristics are used to study the job shop scheduling problem on the basis of the thorough analysis. The main content can be summarized as follows:(1) The basic knowledge of JSP is briefly introduced first, i.e., the description of JSP, the characteristics of the problem, the mathematical model establishment, the expression, the classify, the G&T algorithm and the encoding design method, etc.(2) The migrating birds optimization(MBO) algorithm is adopted to deal with the job shop scheduling problem. To sufficiently express the features of the problem, reasonable encoding and decoding mechanisms are first designed, and a heuristic-based initial population generating method is given to ensure the quality and diversity of solutions in the initial population. Second, in terms of the characteristics of the studied problem, three neighborhood structures are developed to generate the neighboring solutions of individuals. In addition, to enhance the local search ability, the variable neighborhood search algorithm is embedded into the MBO. Finally, five benchmark instances are used to test the proposed improved MBO(IMBO), and the computational results are compared with other algorithms in literatures to verify the effectiveness.(3) The cat swarm optimization(CSO) algorithm is adopted to solve the job shop scheduling problem. First, by considering the characteristics of the problem and the algorithm, the feasible encoding and decoding mechanisms are designed to implement the continuous encoding for the discrete problem. A heuristic-based initial population generating method is given to ensure the quality and diversity of solutions in the initial population. Second, two different searching modes are developed, i.e., seeking mode and tracing mode, and an adaptive behavior mode selection method is also proposed. In addition, the variable neighborhood search algorithm is introduced to the CSO to enhance its local search ability. Finally, five benchmark instances are used to test the proposed improved CSO(ICSO), and the experimental results are compared with the IMBO to verify the effectiveness.