大规模柔性作业车间调度问题分解建模和求解方法

Decomposition Modeling and Solving Method for Large Scale Flexible Job Shop Scheduling Problem

研究在满足既定工序顺序约束的情况下,按序组合工序来分解柔性作业车间大规模调度问题,建立分解调度问题的数学模型,并探索高效求解的方法。首先基于工序组合与遗传算法,将大规模调度问题进行分解降低问题空间复杂度,形成调度子问题,并建立分解后的调度数学模型;其次将利用组合规则生成高质量的初始解,采用遗传算法与蛙跳算法相结合的混合算法,采用双线程进行并行计算求解,提高全局搜索能力和效率,重组后形成原问题的可行解;最后利用实例证实了模型和算法的可行性。

It studies the decomposition of large-scale flexible job shop scheduling problem by sequential combination of processesunder the condition of satisfyingthe constraints of the specified process sequence,establishes a mathematical model of decomposition scheduling problem,and explores an efficient solution method.Firstly,based on the combination of processand the genetic algorithm,the large-scale scheduling problem is decomposed to reduce the space complexity of the problem and to formschedulingsub-problem,After establishingthe decomposed scheduling mathematical model.Secondly,the high-quality initial solution is generated by using the combination rules.Moreover,to improve the global search ability and efficiency,a hybrid algorithm combining genetic algorithm with leapfrog algorithm and parallel computing method with two threads are adopted.After recombination,the feasible solution of the original problem is formed.Finally,the feasibility of the model and algorithm is verified by an example.