无等待流水调度问题迭代启发式算法

针对以总完工时间最小化为目标的无等待流水调度问题(缩写为NWFSP),提出了两个迭代启发式算法(缩写为IHA1、IHA2).一个是以FL(described by Framinan and Leisten,OMEGA,2003)启发式算法产生的解作为初始解,另一个是以WY(described by Hoon-shik Woo and Dong-soon Yim,Computers & Ops Res,1998)启发式算法产生的解作为初始解,然后两者均应用RZ(developed by Rajendran and Ziegler,European Journal of Operational Research,1997)和FL插入以及成对交换技术进行多次迭代来改善解的质量.为了评估,我们使用了Taillard's基准程序随机产生了大量实例,实验结果显示,IHA1和IHA2在解的性能上优于经典的RC1、RC2、PH1(p)算法,随着问题规模的增大,对解的质量改善得更好.     

最小化总完工时间的流水作业调度混合算法

针对有效求解NP难的总完工时间最小流水作业调度问题,提出了一个有效的混合启发式算法产生初始解,并使用禁忌搜索算法对初始解邻域进行搜索的算法框架.基于不同的启发式算法,获得了3个混合禁忌搜索算法HA1,HA2和HA3.使用Taillards基准程序随机产生的大量实例,进行模拟实验,结果表明,所提出的3个算法通过扩大搜索范围提高了解的质量,在性能上均优于目前最有效的启发式算法.与目前最有效的算法相比,产生最好解的平均百分比偏差均下降至少30%,最优解所占比例皆有显著提高.     

流水作业问题的一个启发式算法

讨论具有延迟时间的流水作业问题,并提出了解决该问题的一种启发算法,证明了其最坏性能比是（m 1）/2,并且上界是紧的,特别当m=2,即两台机器上具有延迟时间的流水作业问题时,其最坏性能比是3/2,最后将所得结论推广到FmID2问题,即加工时间相等且延迟时间只取两上值的流水作业问题,其最坏性能比也是m 1/2。     

流水作业调度问题的快速进入启发式算法改进

文章提出了解决流水作业调度问题的改进快速进入启发式算法。这种改进算法遵循原算法中构造双机子问题的基本思想,将原线性权重改进为指数权重并用Johnson双机算法进行求解。改进算法的性能使用了来自文献的实例测试,并与原算法进行比较。比较结果表明,在大规模工件的调度问题中改进算法优于原算法。     

一类装配式流水作业排序问题的启发式算法及其性能比研究

根据Ｆ′２｜ｍ１≥２，ｍ２＝１｜Ｃｍａｘ排序问题是ＮＰ完全问题的论断，提出了ＡＦＳ问题的两个启发式算法，分别给出了应用启发式算法的实例，并证明了该启发式算法在最坏情况下的品性是２的结论     

具有准备时间的流水作业时间表问题启发式算法与最坏性能比分析

本文研究具有准备时间的流水作业时间表问题，给了一个简单的启发式算法，证明了一个简单的启发式算法的最坏性能比是m 1/2(其中m是机器的台数)，且关于上界是紧的，特别当m=2时，该启发式算法的最坏性能比是3／2，此结果要好于Potts在1985年所给出的算法。     

具有学习效应的两台机器流水作业排序问题

讨论了具有学习效应的2台机器流水作业排序问题,目标函数为极小化总完工时间.首先证明了2个相关引理,基于2个引理和对问题的分析,证明了用SPT算法解决问题的界为一个与工件的最小加工时间和最大加工时间相关的且小于2的一个值.     

Flow shop排序问题F2｜prmu｜∑ωjCj的一个启发式算法

给出Flow shop排序问题F2|prmu|∑ωjCj的一个启发式算法，其最坏情况的界为2，且是紧界。此外，还讨论了它的三种多项式可解的条件。     

基于改进遗传算法的Flow Shop调度算法研究

给出了Flow Shop调度问题的数学模型,介绍了三种用于求解该问题的启发式算法,根据普通遗传算法与启发式算法的互补特性,提出了结合两者各自优势的改进遗传算法．通过两个不同规模的经典算例对算法的优化性能进行了对比分析,结果表明,采用了保优策略的改进遗传算法的搜索能力优于启发式算法及普通遗传算法,并具有较强的鲁棒性．     

Flow Shop成组排序问题的调度算法设计及其界的估计

讨论Flow Shop成组排序问题F2│prmu,s,pkij=pij,GT│∑ωjcj.基于WSPT规则,给出求解该问题的一个启发式算法,并证明2是该算法的一个上界.     

流水作业由二台柔性机器组成时的极小完工时间之和问题

该文考虑下述由2台机器组成的流水作业问题:n个相同工件需依相同次序在机器1、2上共进行3次加工.工件j的第一次加工在机器1上进行,所需时间为p1;其第二次加工或单独在机器1上或单独在机器2上进行,当工件j的第二次加工在机器1上进行时,所需时间为p12,当工件j的第二次加工在机器2上进行时,所需时间为p21;其第三次加工需在机器2上进行,所需时间为p2.要求适当安排这n个工件的加工方式以使它们的完工时间之和达到极小.对该问题作者对应不同情况给出了不同的最优解法.     

一类两机器 no-wait 流水作业总完工时间问题

在两机器 no-wait 流水作业问题中,每个工件在加工前有一调整时间,加工完之后有一移走时间,同一工件的调整和移走是可以重叠的,但加工时间不能重叠,同时任一工件在第二台机器上的加工必须紧接在它在第一台机器上的加工之后进行,本文以总完工时间为目标函数,讨论问题最优解中工件排列应满足的条件;其次讨论当工件的三种时间满足一定条件时最优时间表的求法;最后为问题设计了一个近似算法.     

加工时间线性恶化的成组加工流水作业问题

文章讨论了m台机器的Flow Shop成组加工问题.工件在不同机器上的加工时间以相同的系数(斜率)线性恶化.目标函数分别为极小化时间表长和总完工时间.对于目标函数为极小化时间表长的Flow Shop成组加工问题.再进一步细分为组间无调整时间和组间有相同调整时间的两种情形来讨论,都得到了最优调度(排序).对于目标函数为总完工时间的Flow Shop成组加工问题,只要组内按qij单调递增(SPT)序加工,组间按S.单调递增序加工可得最优调度.     

一种解决有限缓冲区流水车间调度问题的复合启发式算法

针对以最大完工时间为目标的有限缓冲区流水车间调度问题,提出了一种新的复合启发式算法.算法设计中首先使用PF-NEH算法进行解空间的搜索,并采用基于插入邻域和交换邻域的可变邻域搜索算法来增强局部搜索.仿真实验表明,该算法具有高效性和优越性.     

基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为 0.4117 ,分支定界算法的效率比较高,处理 100 个工件所用的最大时间不超过 460s 。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。
     

Flow shop排序问题F2|prmu|∑ωjCj的一个启发式算法

给出Flowshop排序问题F2|prmu|∑ωjCj的一个启发式算法,其最坏情况的界为2,且是紧界.此外,还讨论了它的三种多项式可解的条件.     

m台机器上流水作业时间表问题的复杂性及一种新的启发式算法

研究流水作业时间表问题，在具有延迟时间的条件下证明该问题是强NP-困难的．给出一种新的启发式算法，并证明该算法的最坏性能比是(m 1)/2，且上界是紧的．     

可拆分平行机排序问题的一个启发式算法

为缩短工件的完工时间,将极小化最大完工时间的平行机排序问题作为研究目标.在此问题中,允许同一工件拆分成多个子工件在不同的机器上同时加工,同一工件的任何2个子工件不可在同一台机器上加工.与以往研究不同,对工件的拆分方式进行了限制,即工件拆分后所得子工件的长度不能小于给定的阀值,且工件拆分次数尽量少,这是一个NP难问题.借助于LPT算法的思想,提出了一个求解该问题的启发式算法,实现了工件的自动拆分和工件到机器上的自动分配.通过多个实例对文中算法进行了测试,数值结果表明:该算法可行、稳定性良好,适用于工件拆分方式具有类似限制的平行机排序问题的方案决策.     

带单服务器的流水作业时间表问题

研究带单服务器的流水作业时间表问题,目标是使加工时间达到最小,该问题是强NP-困难的．证明即使对于所有安装时间等于1或者所有加工时间等于1的情况下,该问题仍然是强NP-困难的,所以不存在多项式时间的最优解．在只有两台机器的情况下,引入了一人新的启发式算法,并证明该算法的紧界为3／2．     

基于经济学的启发式网格资源调度算法

针对网格环境中资源调度的复杂需求,将现实世界中的经济原理和模型应用到网格环境下的资源调度中,并据此提出一种基于经济学的资源调度算法.首先,基于经济学中的一般均衡理论,结合集中式定价算法收敛速度快,以及分布式WALRAS算法扩展性好的优点,提出一种新的定价算法,提高定价速率;其次,提出一种能兼顾考虑资源调度的服务质量.时间以及费用的启发式算法,能更好地满足用户需求及开放复杂的网格环境.