基于网络流的多并行机可中断开放车间调度算法

作     者：展勇 邱长华 祝海涛 ZHAN Yong;QIU Chang-hua;ZHU Hai-tao

作者机构：哈尔滨工程大学机电工程学院黑龙江哈尔滨150001 

基　　金：黑龙江省科技攻关计划资助项目(CB07G109) 中央高校基本科研业务费专项资金资助项目(HEUCF100705)~~ 

出 版 物：《计算机集成制造系统》 (Computer Integrated Manufacturing Systems)

年 卷 期：2011年第17卷第5期

页      码：990-996页

摘      要：为提高开放车间的生产效率,研究了多并行机可中断开放车间调度问题,提出了基于网络流的调度算法。针对车间的特点,建立了以制造期最短为目标的整数规划模型,提出了工件有就绪时间约束时制造期下界的计算方法。采用网络流理论表示机器与工件间的分配关系和时间约束,建立了开放车间的网络流模型,将调度问题转换为最大流问题。引入最小负载优先和最大工作量优先两条启发式规则,设计了基于预流推进的最大流算法,并针对最大流算法中存在的局部优化问题,提出了最大流优化方法,得到机器资源的分配结果。在此基础上,建立了加工时间矩阵及减量集合,求得各机器上工件的加工顺序。使用两组随机数据对算法进行了实验,通过与制造期下界的对比,验证了算法的正确性。

主 题 词：开放车间 调度 并行机 网络流 整数规划 调度算法 

学科分类：0808[工学-自动化类] 0809[工学-计算机类] 0817[工学-轻工类] 08[工学] 0807[工学-电子信息类] 0802[工学-机械学] 0835[0835] 0811[工学-水利类] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13196/j.cims.2011.05.96.zhany.027

馆 藏 号：203356449...