Multi-stage ordinal optimization based approach for job shop scheduling problems

摘要

In this paper, a multi-stage ordinal optimization (OO) based approach is proposed to solve for a good enough schedule of stochastic classical job shop scheduling problems using limited computing time. The proposed approach consists of exploration and exploitation stage. The exploration stage uses a genetic algorithm (GA) to select a good candidate schedule set, and the fitness in GA is evaluated using a rough model, the artificial neural network. The exploitation stage is composed of multiple substages. The more refined crude models for evaluating a candidate schedule employed in these substages are stochastic simulations of various lengths ranging from very short (crude model) to very long (exact model). The candidate schedule set in each substage resulted from previous substage will be reduced gradually. In the last substage, the exact model is used to evaluate all the remaining schedules in the most updated candidate schedule set, and the one with the best objective value is the good enough schedule that we seek. The proposed approach is applied to a stochastic classical job shop scheduling problem comprising 6 jobs on 6 machines with random processing time of truncated normal, uniform, and exponential distributions. The simulation results demonstrate the quality of the solution obtained by the proposed approach in comparison with five dispatching rules. The results also demonstrate the computational efficiency of the proposed algorithm.