求解一类柔性装配流水车间调度问题的混合分布估计算法

A hybrid estimation of distribution algorithm for a certain kind of flexible assembly flow shop scheduling problem

针对生产装配车间广泛存在的一类带不同工序的柔性装配流水车间调度问题(Flexible Assembly Flow Shop Scheduling Problem with Different Process,FAFSSP_DP),提出了一种混合分布估计算法(Hybrid Estimation of Distribution Algorithm,HEDA),用于优化最大完工时间(makespan)。首先,以2维概率矩阵作为概率模型,进而构造一种基于变量相关性的概率模型更新机制,用于学习优良解对应变量间的相关关系信息和序关系信息,并以此对概率模型进行更新,使得算法的全局搜索具有较好的引导性;其次,引入带首次改进跳出策略的Insert邻域搜索来加强算法的局部搜索能力,从而有助于算法在全局和局部搜索之间达到合理平衡。仿真实验和算法的比较验证了HEDA的有效性。

Scheduling plays a key role in manufacturing systems of the enterprise for maintaining competitive position in the fast changing market. The flexible assembly flow shop scheduling problem（FAFSSP） is a typical scheduling problem, which is of strong engineering background and among the hardest combinatorial optimization problems. In this paper, a certain kind of FAFSSP, namely, flexible assembly flow shop scheduling problem with different process（FAFSSP_DP）, is considered, which is more complex but more practical than FAFSSP. In FAFSSP_DP, two production stages（i.e., the first stage and the second stage） are utilized to produce accessories, and one assembly stage（i.e., the third stage） is used to assemble the produced accessories into the final product. That is, the first stage and the second stage can be modeled as a complex two-stage flow shop with parallel machines at each stage, and the third stage can be modeled as a single machine shop. Since FAFSSP has been proved to be NP-hard and it reduces to FAFSSP_DP, it can be concluded that FAFSSP_DP is also NP-hard. Due to the computation complexity of FAFSSP_DP, exact solution techniques are only applicable to small-scale problems and constructive heuristics cannot achieve satisfactory solutions. Thus, it is very important to design meta-heuristics or evolutionary algorithms for addressing FAFSSP_DP. Recently, a novel probabilistic-model based evolutionary algorithm, i.e., an estimation of distribution algorithm（EDA）, was presented for dealing with the traveling salesman problem and the job shop scheduling problem. EDA utilizes a probabilistic model to generate new population and guide the search direction. The evolution process of EDA can be regarded as a process of competitive learning, whose probability model is updated by using the valuable information of the better solutions at each generation. Because of its simple framework and outstanding global exploration ability, EDA has attracted much attention and has been successfully used to solve some production scheduling problems. Thus, this paper proposes a hybrid estimation of distribution algorithm（HEDA） to optimize the makespan criterion for FAFSSP_DP. Firstly, a two-dimension probabilistic matrix is selected as the probabilistic model, and then a probabilistic model update mechanism based on variable correlation is constructed to learn the ordinal information of production in the excellent solution set and update the probabilistic model, which can make the global search efficiency of HEDA better. Secondly, the Insert-based neighbor search with first-improve-skip strategy is utilized to enhance the local search ability of HEDA, which is helpful for the proposed algorithm to achieve the reasonable balance between the global and local search. Finally, the design of experiment（DOE） method is used to analyze the influence of HEDA’s key parameters and set these key parameters to the appropriate values. To investigate the performance of HEDA, computational simulation is carried out with some randomly-generated instances under different scales. Moreover, two effective heuristics and four effective meta-heuristics in the international journals are selected to compare with the proposed algorithm. Simulation results and comparisons demonstrate that the effectiveness of the HEDA in solving the FAFSSP_DP. The future research work is to develop effective EDA for dynamic multi-objective FAFSSP_DP.