基于遗传算法和分枝定界的多车间空闲产能调度方法

Multi-shop Idle Capacity Scheduling Method Based on Genetic Algorithm and Branch and Bound

个性化产品具有多变的产品结构和复杂的加工特征,使得单一车间难以满足如此广泛的加工参数,需要借助外协车间才能完成生产任务。每个外协车间负载不同,空闲时段也不同,为了提升这些时间的利用率,提出基于遗传算法和分枝定界的混合调度方法。设计基于混合优化策略的动态重调度机制,将动态的生产过程转化为一系列在时间上连续的静态调度问题;建立以最小化总拖期为目标的数学模型;采用遗传算法和分枝定界方法对调度过程中的两个阶段分别进行优化,即在每个事件时刻采用遗传算法生成预调度方案并划分为已派工部分、待派工部分和可调整部分,在已派工部分正在执行的时间段采用分枝定界方法对可调整部分进行改进优化。采用运筹学优化器OR-Tools验证所提模型的正确性。试验数据表明,与单一方法相比,混合方法在所有实例上获得改进,验证了所提方法是有效可行的。

Personalized products have variable BOM structures and complex processing parameters, making it difficult for a single workshop to meet such a wide range of processing parameters, and requiring cooperation with external workshops to expand capabilities of processing.Since each workshop has different loads and different idle periods, a hybrid scheduling method based on genetic algorithm(GA) and branch and bound(BB) is proposed to improve the utilization of the idle periods. Firstly, a dynamic rescheduling mechanism based on a hybrid optimization strategy is designed to transform the dynamic production process into a series of static scheduling problems that are continuous in time. Then, a constraint programming model with the objective of minimizing the total tardiness is established;Finally, GA and BB method are used to optimize the two phases of the scheduling process, that is, GA is used to generate a pre-scheduling scheme at each event moment, and the scheme is divided into the dispatched part, the to-be-dispatched part and the adjustable part, and the BB method is used to optimize the adjustable part during the execution period of the dispatched part. Google OR-Tools is used to verify the correctness of the proposed model. The simulation experiments show that the hybrid method obtains improvements on each instance compared to the single method, verifying that the proposed method is effective and feasible.