基于网络流的开放式车间调度问题研究

发布时间：2020-05-17 16:16

【摘要】：开放式车间调度问题(Open-Shop Scheduling Problem)也称为自由作业调度问题,是作业车间调度问题的一种特殊形式。开放式车间调度问题因应用领域广泛受到人们的重视,本文研究一类带有并行机的开放式车间调度问题,其中工件具有时间窗约束,加工过程允许中断,但不允许延期,分别求出问题的可行调度结果以及以最小制造期为目标的最优调度结果。 本文将开放式车间调度问题的求解过程分解为资源分配和排序两个阶段。在资源分配阶段,首先建立了开放式车间的线性规划模型,然后将线性规划模型转化为网络模型,在网络模型中机器和工件用节点表示,车间的各种约束条件用弧的容量约束表示,最后,通过网络最大流算法求得了开放式车间的可行调度结果,并在此基础上通过含参最大流网络对分配结果进行优化,得到了以最小制造期为目标的开放式车间的调度结果。在排序阶段,首先制定规则将分配到并行机组的加工时间分配到每台并行机,然后分别建立每个时间段内的加工时间矩阵,通过在各矩阵中选择减量集合得到最终调度结果。 最后,通过算例分析初步验证了算法的正确性,并在VC++6.0环境中以SQL Server 2000作为后台数据库开发了开放式车间调度系统原型。该系统具有友好的交互界面,并能够以甘特图的形式直观的给出调度结果。
【图文】：

加工2个时间单位，工件4在机器3上加工1个时间单位。再次更新加工时间矩阵发现所有元素都为零，排序完成。根据以上计算过程得到调度的甘特图如图4.7所示。机器1机器2机器3图4.7调度甘特图4.6本章小结制定了本文开放式车间调度问题的总体方案，通过数据预处理、分配问题求解、分配结果排序实现了开放式车间调度问题的可行性调度。分配问题求解阶段分别通过求解两个最大流网络得到最终分配结果;排序阶段制定了并行机组平衡负载规则，通过在加工时间矩阵中构造减量集合求得了开放式车间调度问题的可行调度结果。

可行调度与最有调度甘特图
【学位授予单位】：哈尔滨工程大学
【学位级别】：硕士
【学位授予年份】：2010
【分类号】：TH186

【相似文献】

相关期刊论文 前10条

1 刘婷;;变点交叉多目标遗传算法在作业车间调度中的应用[J];大连交通大学学报;2011年04期

2 朱，

本文编号：2668834