文摘
论述了流水车间调度问题和发布日期最大完工时间最小化。通过测序工作,得到改进的启发式算法来处理大型问题。此外,一些性质的基础上,提供了本地搜索方案来提高中等程度的启发式来获得高质量的解决方案的问题。提出了一种sequence-independent下界来评估算法的性能。一系列的仿真结果验证了该算法的有效性。
1。介绍
在流水车间调度模型中,每个工作都必须被处理以相同的顺序在一组机器上。目标是确定工作序列优化某一预定的目标函数。在任何给定的时间,每台机器最多只能处理一个工作,每个工作最多可以由一台机器。与此同时,每个作业不能被抢占的其他工作。流水车间调度问题广泛存在于工业生产和机械制造业。例如,在炼钢过程中,钢液由连铸机铸出到中间板;被热炉加热后,在轧机板滚成产品。显然,这是一个典型的流水车间生产模式。因为大多数是强np难的问题,是不可能在多项式时间内获得全局最优的解决方案。所以流水车间调度算法的研究是非常重要的对于减少运行时间和提高生产力。
自从第一次调度规则提出了由约翰逊(1]两考组成的流水车间问题的目标(即。,the maximum completion time) minimization, many works have been conducted on this research area. A comprehensive survey of flow shop makespan problems by 2010 can be found in Potts and Strusevich [2]或白和任3]。最新的研究提到了如下工作。答:Rudek和r . Rudek4]证明了普通工作时的最大完工时间两流车间的np困难问题处理时间被不减少的位置相关的功能(老化效应)和至少一个机器上表示强np困难如果工作在两台机器上处理时间是不同的。Aydilek和Allahverdi5)提出了一个多项式时间的启发式算法两流水车间分批发布日期的问题。的最大完工时间最小化机流水车间学习考虑问题,钟和通6)提出了一个优势定理和一个下界加速和算法寻求最优解决方案。考的标准在流水车间模型中,一个高性能的建设性的启发式应提出一个有效的打破僵局的策略是和林(7提高解决方案的质量。同样,古普塔et al。8)提出了一种启发式算法与基准相比,帕默,cd,和NEH算法,来解决工作和最大完工时间最小化机流水车间调度问题。对与工作相关的标准,结果白(9)提出了最短的处理基于时间的算法的渐近最优的流水车间问题优化二次总完工时间和发布日期。白和张10结果扩展到一个总目标、总力量完成时间()。
本文的流水车间调度问题最小化最大完工时间的发布日期是解决。相反的静态设置同时工作,工作到随着时间的推移,根据他们的发布日期,这更紧密地接近实际调度环境。Lenstra et al。11]证明两流水车间分批发布日期是强np困难问题。这意味着无法找到这个问题的最优解在多项式时间内;启发式算法可能会更有效的获得一个大型问题的近似解。因此,一种新的修改GS算法(MGS)算法的基础上,冈萨雷斯和萨尼(12)提出了减缓商店最小化时间发布日期。然后提供一个改善计划来促进MGS算法的性能。此外,sequence-independent下界的问题。计算实验揭示MGS算法的性能,改进的方案,和下界在不同大小的问题。
本文的其余部分组织如下。问题是制定节2,MGS算法和改进的方案提供了部分3和4,分别。新的下界和计算结果给出了部分5。摘要与结论部分关闭6。
2。问题陈述
在流水车间问题,一组工作上处理不同的机器在同一个订单。工作,,处理机器,负的处理时间和一个发布日期工作,这是最早的时间是允许的过程。每台机器最多只能处理一个工作,每个工作最多可以由一台机器在任何给定的时间。流程工作的机器,先到先得的方式。排列时间表是本文和中间存储之间的连续的机器是无限的。工作的完成时间,,在机,,是用。确定工作目标是最小化最大完工时间的序列,即。
3所示。修改后的GS算法
冈萨雷斯和萨尼(12]介绍了GS算法解决流水车间极小化问题。基于其想法,提出了一种新的启发式修改GS (MGS)算法来处理发布日期的流水车间极小化问题。一个正式的表达MGS算法如下。
3.1。MGS算法
步骤1。把机器到组。
步骤2。为每台机器组,,当机成为闲置或者新的就业机会到来,过程通过约翰逊的规则(即可用的工作。,首先安排的工作在不减少的订单然后在nonincreasing顺序安排剩余的工作,在那里表示工作的处理时间在集团在机,);如果没有工作,去一步3。
步骤3。等到工作去一步到达2。如果所有的工作已经安排,去一步4。
步骤4。终止程序和计算的客观价值的时间表。选择至少一个作为最终的解决方案,。
算法的流程图如图1。提出一个例子展示MGS算法的执行。
例1。流水车间调度问题涉及三个机器,,,和四个职位,,,,发布日期。发布日期和处理时间下面列出的工作。问题的目标函数。考虑
最后MGS算法的序列。和客观的价值。调度过程如图2。
4所示。改进的方案
进一步促进了中等规模的问题解决方案的质量,最大完工时间两流车间的一些性质和问题提出了发布日期如下。
属性1。对问题如果两个相邻的工作和满足(我) ,(2) 和,(3) ,然后最优序列的工作将之前的工作。
证明。定义的两份工作的完成时间序列和被和分别。因此,对于序列, 对序列, 分,获得它 请注意, 因此, 表明序列的最优性。
属性2。对问题如果两个相邻的工作和满足(我) ,(2) 和,(3) ,然后最优序列的工作将之前的工作。
证明。定义的两份工作的完成时间序列和被和分别。因此,对于序列, 对序列, 分,获得它 请注意, 因此, 表明序列的最优性。
财产3。对问题如果两个相邻的工作和满足(我) ,(2) 和,(3) ,然后最优序列的工作将之前的工作。
证明。定义的两份工作的完成时间序列和被和分别。因此,对于序列, 对序列, 分,获得它 请注意, 因此, 表明序列的最优性。
性质4。对问题如果两个相邻的工作和满足(我) ,(2) 和,(3) ,然后最优序列的工作将之前的工作。
证明。定义的两份工作的完成时间序列和被和分别。因此,对于序列, 对序列, 分,获得它 请注意, 因此, 表明序列的最优性。
这些属性,提供一个改善计划促进MGS算法获得的原始解决方案。在一个正式的表达改善方案,,,表示工作中发现原始序列的位置,表示比较的数量的工作按顺序比较的th工作对于一个给定的工作在一个种子序列,表示比较的数量从目前的工作结束工作,表示数量的组和表示通过交换的一组序列生成th的工作种子序列中的每个不同的工作。表达式的格式可以概括如下。
4.1。改进的方案
步骤1。生成初始序列MGS算法和计算客观价值。
步骤2。集,,。
步骤3。比较工作推进下(如果,设置在序列)工作。如果这两个职位和满足(1) ,(2)下列条件之一:(我) ,(2) ,(3) ,(iv) ,然后交换工作,计算出客观价值,继续步骤4。
步骤4。如果客观价值步中获得3小于,设置并确定序列,这样。如果,设置并返回到步骤3;否则,继续步骤5。
步骤6。 是最后的时间表。停止。
5。计算结果
在本节中,一系列的计算实验旨在揭示了该算法的性能和改进方案在不同大小的问题。十个不同的随机测试的每个组合参数,分别进行,平均报告。所有的算法在MATLAB R2012a编码和实现PC与英特尔酷睿i7 - 2600 CPU (3.4 GHz×4)和4 GB RAM。工作的处理时间离散均匀分布随机生成的离散正态分布与期望方差5.5和1.72。
评估算法的性能问题,白等。13提出了一个下界():
然而,的价值因为有时候可能大于最优价值是顺序相依。考虑下面的例子。
例2。两流车间调度问题涉及两个工作,和,发布日期。发布日期和处理时间下面列出的工作。这个问题的目的是: 对序列,计算的价值: 和最优调度的问题。相关的最优值 很明显,。
严格保证下界值小于最优值,一个新的下界()提供:
很明显,最后两个项目保证工作的下界是独立的序列。
定理3。我们的处理时间,,,独立随机变量有相同的连续分布的密度上定义。然后,对于每一个,的概率,
证明。不失一般性, 分双方(28),以限制, 白等。13)证明 结合(29日)和(30.)收益率定理的结果3。
计算例子2与:
5.1。测试MGS算法
一些数值试验进行了揭示MGS算法的有效性。三,五,十机和50岁,100年,200年,500年,分别测试和1000个工作岗位。发布日期是来自一个离散均匀分布,在那里工作岗位的数量和吗是一个乘数的值1、2,5,8。DSJF启发式算法提出的白和唐14)作为参考比较。首先,在表1和2,我们比较MGS算法的性能和DSJF启发式采用相对百分比%,MGS算法和客观价值的吗DSJF启发式的客观价值。
在表中1和2数据表明,两种算法的性能取决于乘数。为了进一步确定这两种算法的优势,在表3和4我们执行以下实验意味着相对百分比%,表示时间DSJF启发式主导MGS算法。
结果表3和4表明DSJF启发式完全主宰MGS算法和相反的情况。因此,在这两种情况下,获得适当的算法解决方案的一个直接算法更为实用。为了演示MGS算法的渐近最优性,我们比较与的相关价值的客观价值。平均相对百分比×100%是使用,MGS算法和客观价值的吗客观的价值吗。
表中的数据5和6表明MGS算法的渐近最优性。相反,固定数量的就业岗位,比率扩大机器的数量从3增加到10。原因可能是更大的机器的数量,数量的空闲时间越大,扩大的价值目标之间的差距及其下界。
5.2。测试改进方案
我们比较的有效性改善计划(是)与DSJF启发式/ MGS算法。在表中7和8,意思是相对比例×100%被雇佣,的客观价值DSJF启发式/ MGS算法和吗是客观的价值。三,五,十20到50个工作机器测试,分别。乘数的值0.1,0.04(50工作)和0.05(20工作)。工作的处理时间离散均匀分布随机生成的。
结果表明,改进后的方案有效提升算法的性能中等程度问题。随着问题规模和发布日期的范围继续扩大,改进是削弱和运行时间延长。因此,获取算法的解决方案与MGS算法直接用于大规模问题更实用。
6。结论
本文提出了一种改进的启发式算法,也就是说,MGS算法,发布日期的流水车间极小化问题。并介绍了一种改进的方案来提高原始的质量解决方案。评估算法数值,一个新的下界序列提供了独立的问题。计算结果表明MGS算法的优势和改进方案的有效性。
利益冲突
作者宣称没有利益冲突有关的出版。
确认
这部分工作是由中国国家自然科学基金(61473073,61473073,61203329),基础研究基金为中央大学(N130417006 N110417005),沈阳城市的科技计划项目(f11 - 264 - 1 - 63),为辽宁高校优秀人才和项目(LJQ2014028)。