AN EFFECTIVE USE OF HYBRID METAHEURISTICS ALGORITHM FOR JOB SHOP SCHEDULING PROBLEM

作者：Zhang, H.^*; Liu, S.; Moraca, S.; Ojstersek, R.

来源：International Journal of Simulation Modelling, 2017, 16(4): 644-657.

DOI：10.2507/IJSIMM16(4)7.400

• Job Shop Scheduling Problem
• Metaheuristics Algorithm
• Shuffled Frog Leaping Algorithm
• Path Relinking
• Random Multi-Neighbourhood Structures

This paper presents an effective use of hybrid metaheuristics algorithm for solving Job Shop Scheduling Problem (JSSP). Integration of three metaheuristics algorithms: Shuffled Frog Leaping Algorithm (SFLA), Intelligent Water Drops algorithm (IWD) and Path Relinking (PR) algorithm were put together to solve JSSP. First, simulation model was developed and tested on the test data of Traveller Salesman Problem (TSP). Second, the model was tested on real world production line to solve the problem of Minimum Needed Workers (MNW) at the production line. The model enables individual test of three mentioned algorithms and calculation of new proposed Random Multi-Neighbourhood based Shuffled Frog Leaping Algorithm with Path Relinking (RMN-SFLA-PR). Experiments were tested on two software environments MATLAB and Simio, which gives us reliable, robust and tangible results. Results show that the new proposed RMN-SFLA-PR algorithm converged to optimum almost ten times faster than individual algorithms. The most important thing is the successful rate of all independent runs of the proposed RMN-SFLA-PR is 100 % in low-dimensional cases of the 4 benchmarks (dj38) and in JSSP to solve MNW for the real world production line.

• 出版日期2017-12
• 单位北京交通大学