带准备时间的异构并行机调度规则自动设计方法

Automatic Designing of Scheduling Rules for Heterogenous Parallel Machines with Setup Time

以大规模定制化的家电行业生产为背景,将家电总装产线的投产排序决策抽象成为一类带准备时间的异构并行机动态调度问题。针对人工调度规则解决动态调度问题简单高效,但场景适应性弱的特点,引入了基于遗传规划(genetic programming,GP)的规则自动设计框架。首先,通过分析家电总装产线生产特征以及优化需求,以最小化平均拖期为优化目标,建立异构并行机调度模型;随后,针对问题特征,构建线体指派-工单排序规则对协同进化的改进型GP算法,并提取线体、工单的特征属性输入GP算法框架以自动设计调度规则。最后,基于某家电企业实际案例数据设计大量算例测试集,通过对比GP算法与人工设计规则在差异化工况场景的实验结果,验证GP算法有效性,并进一步分析了GP算法构造规则受不同生产环境参数的影响。

Taking massive customized production of home appliance as the research background,the scheduling of home appliance manufacturing is abstracted as a problem of dynamic heterogenous parallel machine scheduling with sequencedependent setup time(HPMS-SST).Manual scheduling rules are simple and efficient in solving dynamic scheduling problems,but their adaptability to different scenarios is weak.To this end,an automatic design framework for rules based on genetic programming(GP)is introduced.First,by analyzing the features and optimization requirements of home appliance production,a model of HPMS-SST is established with the objective of minimizing the mean product tardiness.Subsequently,based on the characteristics of this problem,an improved GP algorithm is proposed for the coevolution of machine assignment and queue sequencing rules;Also,the feature attributes of machines and orders are extracted and input into the GP algorithm framework to automatically design scheduling rules;Finally,a number of test cases are generated from the real production data of a home appliance manufacturer.By comparing the experimental results of the proposed algorithm and manual designed rules in various conditions,the effectiveness of the GP algorithm is verified.Besides,sensitive analysis is conducted to evaluate the influence of parameters for different production conditions on the generated GP-based rules.