A Robust Optimization Approach For Flexible Job Shop Scheduling Problem Under Uncertainty

The flexible job shop scheduling problem (FJSP) under uncertainty is a kind of typical production scheduling problem. The problem is expanded to be stochastic, dynamic, discrete and complex, and become more close to the actual production. Thus, researches for effective algorithms to address uncertain FJSP have been an important topic in production scheduling and optimization.First of all, a robust optimization approach is proposed to address FJSP under uncertain processing times to increase the feasibility of schedules, and ensure the stability of production process. Two parameters, including the uncertainty level and the unreliability level, are introduced to describe variables disturbance and constraints violence respectively. Assuming that uncertain variables are expressed as probability distribution, the common robust optimization framework of general linear programming problems is formulated, and thus applied to transfer the NP-hard original problem into its deterministic robust counterpart.Secondly, in order to meet the decision need of operation sequence and machine assignment in the FJSP, the double layer encoding based on procedure codes and machine codes is adopted, and the greedy algorithm is used to achieve the active scheduling decoding. The fitness function with stochastic processing time is designed to evaluate chromosomes of uncertain scheduling problems. The mutation operation, combined with neighborhood improvement ability of the neighborhood search, is developed to drive a robust optimization algorithm.Finally, a typical case and some benchmarks are taken to make experiments. Statistic results show that the proposed approach can obtain the deterministic robust counterpart model of FJSP when the processing time disturbance is expressed as the uniform distribution from-1to1, and the proposed algorithm can obtain the optimal solutions of all cases within95%confidence level in a short computational time and at reasonable productivity loss.