%0 Journal Article
%T 基于网络流的多并行机可中断开放车间调度算法
%A 展勇
%A 邱长华
%A 祝海涛
%J 计算机集成制造系统
%P 0-0
%D 2011
%X 为提高开放车间的生产效率，研究了多并行机可中断开放车间调度问题，提出了基于网络流的调度算法。针对车间的特点，建立了以制造期最短为目标的整数规划模型，提出了工件有就绪时间约束时制造期下界的计算方法。采用网络流理论表示机器与工件间的分配关系和时间约束，建立了开放车间的网络流模型，将调度问题转换为最大流问题。引入最小负载优先和最大工作量优先两条启发式规则，设计了基于预流推进的最大流算法，并针对最大流算法中存在的局部优化问题，提出了最大流优化方法，得到机器资源的分配结果。在此基础上，建立了加工时间矩阵及减量集合，求得各机器上工件的加工顺序。使用两组随机数据对算法进行了实验，通过与制造期下界的对比，验证了算法的正确性。
%K 开放车间
%K 调度
%K 并行机
%K 网络流
%K 整数规划
%K 调度算法
%U http://www.cims-journal.cn/CN/abstract/abstract3023.shtml