禁止拖期交付的无等待流水车间调度问题算法研究  

Research on Modeling and Algorithm of No-Wait Flow Shop Scheduling Problem with Prohibited Tardiness

作　　者：宋存利[1] SONG Cunli(Software Institute,Dalian Jiaotong University,Dalian 116052,China)

机构地区：[1]大连交通大学软件学院,辽宁大连116028

出　　处：《大连交通大学学报》2018年第6期100-105,共6页Journal of Dalian Jiaotong University

基　　金：辽宁省自然科学基金资助项目(201602130;20170540141)

摘　　要：在分析禁止拖期交付的无等待流水车间调度问题特征的基础上,建立了该问题的混合整数规划模型,提出了基于有向无环图的精确搜索算法ESA.该算法保证了对小规模问题的精确求解,而对稍有规模的问题,ESA算法效率较低,因此在ESA算法基础上又提出了基于ESA的分段迭代搜索算法SISA-ESA,从而保证了算法能在较短时间内找出问题的较优解.最后进行了仿真实验,将此算法的运行结果与传统算法的运行结果进行比较,实验证明了所提出的算法的有效性和可行性.Based on analyzing the characteristic of no-wait flow shop scheduling problem with prohibited tardiness,an hybrid integer programming model is built,and three properties are proposed.Then an exact searching algorithm(ESA)based on acyclic graph is proposed.Experiment results show that the algorithm can find the accurate solution for the small sized problem during a short time.However,the algorithm needs a long time to search the accurate solution for a large sized problem.Therefore a new segmented iterative searching algorithm based on ESA is proposed(SISA-ESA).Compared with the traditional heuristic algorithms,the experiment results show that the new algorithm can find the optimal solution in a very short time for large sized problem with due date,which shows the feasibility and effectiveness of the algorithm.

关 键 词：无等待流水车间 精确搜索算法 交货期 最小化完工时间 

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