染缸排产建模及滑动时间窗启发式调度算法  

Modeling of dyeing vat scheduling and slide time window scheduling heuristic algorithm

作　　者：隗千千 董兴业[1] 王焕政 WEI Qianqian;DONG Xingye;WANG Huanzheng(School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China)

机构地区：[1]北京交通大学计算机与信息技术学院

出　　处：《计算机应用》2020年第1期292-298,共7页journal of Computer Applications

摘　　要：针对染缸排产问题约束复杂、任务规模大、排产效率要求高的特点,为了提高问题模型和算法在实际场景中的适用性,建立了染缸排产增量调度模型,提出了滑动时间窗启发式调度(STWS)算法。该算法以最小化延误代价、洗缸成本、染缸切换成本为优化目标,使用启发式调度规则,按照优先级顺序调度产品;对于每个产品的调度,先用动态拼缸算法和拆缸算法进行批次划分,然后调用批次最佳排序算法调度批次。使用某染纱企业车间实际生产数据仿真调度,所提算法可在10 s内完成月度计划的调度。相对于人工排产方式,所提算法提高了排产效率,显著优化了三个目标,在增量调度中洗缸成本和染缸切换成本也有明显优化。实验结果表明所提算法具有很好的调度能力。Considering the characteristics of dyeing vat scheduling problem, such as complex constraints, large task scales, high efficiency request, an incremental dyeing vat scheduling model was established and the Slide Time Window Scheduling heuristic(STWS) algorithm was proposed to improve the applicability of the problem model and the algorithm in real scenario. In order to meet the optimization target of minimizing delay cost, washing cost and the switching cost of dyeing vat, the heuristic scheduling rules were applied to schedule the products according to the priority order. For each product scheduling, the dynamic combination batch algorithm and the batch split algorithm were used to divide batches, and then the batch optimal sorting algorithm was used to schedule the batches. The simulated scheduling results on actual production data provided by a dyeing enterprise show that the algorithm can complete the scheduling for monthly plan within 10 s. Compared with the manual scheduling, the proposed algorithm improves the scheduling efficiency and significantly optimizes three objectives. Additionally, experiments on incremental scheduling show obvious optimization of the algorithm on reducing the washing cost and the switching cost of dyeing vat. All the results indicate that the proposed algorithm has excellent scheduling ability.

关 键 词：染缸排产 启发式算法 增量调度模型 异构并行机 批处理调度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301[自动化与计算机技术—控制科学与工程]