An effective Markov network based EDA for flexible job shop scheduling problems under uncertainty

This paper presents a min-max regret version programming model for the stochastic flexible job shop scheduling problem (S-FJSP) with the uncertainty of processing time. An effective Markov network based estimation of distribution algorithm (EDA) is proposed to solve S-FJSP to minimize its maximum regret. The proposal employs Markov network modeling machine assignment where the effects between decision variables are represented as an undirected graph model. Furthermore, min-max regret metric based assessing algorithm is used to measure the robustness, where a critical path-based local search method is adopted to achieve better performance. We present an empirical validation for the proposal by applying it to solve various benchmark flexible job shop problems.