全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

, PP. 0-0

Keywords: 开放车间,调度,并行机,网络流,整数规划,调度算法

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[1]  PRINS C. Competitive genetic algorithm for the open-shop scheduling problem[J]. Mathematical Methods of Operations Research,2000,52(3):389-411.
[2]  QUEYRANNE M,SVIRIDENKO M. A(2 +ε)approximation algorithm for the generalized preemptive open shop problem with minsum objective[J]. Journal of Algorithms,2002,45(2):202-212.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133