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

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

基于插入-分段的无等待流水作业调度复合启发式算法

为求解NP-难的总完工时间最小化的无等待流水作业调度问题,提出一种有效复合启发式算法.通过分析基本操作的目标增量性质,构造基于插入-分段(I-S)的邻域结构和操作,提出了基于I-S的复合启发式算法(ISCH).ISCH算法与基于比较的启发式算法(BE)、基于置换的复合启发式算法(PH1(p))、Framinan等提出的复合启发式算法(FNM)和基于可变邻域搜索的混合遗传算法(GA-VNS)的比较结果表明,ISCH算法性能最佳,其平均相对偏差的均值较BE算法降低2.04%,平均运行时间为FNM算法的18.43%.当存在时间约束时,ISCH算法的平均相对偏差较GA-VNS算法降低0.99%.该算法中,目标增量方法的选用降低了运行时间,基于I-S邻域结构的方法则提高了算法性能.     

最小化加权绝对偏差的并行多机调度问题

用禁忌搜索算法（ＴＳ）求解带有最小化绝对偏差的并行多机调度问题，首先证明了它是一个ＮＰ－难题，然后用一个启发式作初始解，给出一个禁忌搜索算法，实验表明，禁忌搜索方法求解最小化加权绝对偏差问题可以获得最优解或近似最优解。     

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

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

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

针对以总完工时间最小化为目标的无等待流水调度问题(缩写为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)算法,随着问题规模的增大,对解的质量改善得更好.     

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

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

加权总完工时间有限的资源约束单机排序问题

讨论工件加工时间依赖于分配给它的一类资源，且加权总完工时间有限，目标函数为极小化资源总量的单机排序问题，对问题1，给出了一个有关最优解中最优资源使用的重要性质并利用该性质，对于bj=b，wj=w,aj=a这种特殊情况给出了最优算法．     

智能混合优化策略及其在流水作业调度中的应用

通过结合蚁群算法(ACO)的并行搜索结构和模拟退火算法(SA)的概率突跳性,提出了一种有效的混合优化策略,并将该策略应用于流水作业调度问题(FSP)．在该策略中,蚁群系统的一个周游路线为模拟退火算法提供了一系列初始解,在每个退火温度上进行抽样准则检验并产生新解,然后更新信息激素;蚁群算法再利用模拟退火算法产生的新解进行并行搜索．同时,根据此策略构建并实现了针对FSP问题求解的具体混合算法．仿真结果表明,混合算法弥补了ACO易陷入局部最优和SA搜索效率较低的缺点,增强了全局搜索能力,在求解FSP调度问题的性能上也优于其他算法。     

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

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

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

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

基于禁忌搜索的神经网络集成

给出了一种利用禁忌搜索来实现神经网络集成AdaBoosting算法的方法。以Ada- Boosting算法中的权值向量为优化对象,对其若干个元素进行扰动,并通过设定其为禁忌对象,以禁忌搜索控制寻优方向,以逼近误差为适值函数,在满足逼近误差或达到进化代数时结束进化。由于禁忌搜索可以避免迂回搜索,从而提高进化效率,使得算法易收敛。通过实例验证了该方法的可行性。     

定位路线问题的两阶段禁忌搜索算法研究

定位路线问题是定位配给和车辆路线问题的集成。分析了定位路线问题的含义,建立了此问题的数学模型,并用Lingo 10.0验证了模型的正确性。由于该模型属于NP-hard问题,设计了两阶段禁忌搜索算法:第一阶段用禁忌搜索算法求解定位配给问题,确定设施定位及客户分配;第二阶段用禁忌搜索算法求解车辆路线问题,经过两个阶段的多次迭代求得定位路线问题的优化解,通过实例计算验证该算法的可行性和有效性。     

基于禁忌搜索算法的计算机通信网络中容量与流量分配问题的优化研究

为了降低网络的运营费用与改进网络性能，首次采用近年来新出现的一种高效的现代超启发式搜索方法——禁忌搜索算法求解计算机通信网络中链路容量与流量分配(CFA)问题，讨论了计算机通信网络中链路的固定费用、时延费用与可变费用对运营总费用的影响．大量的计算机仿真实验结果不仅验证了禁忌搜索算法对求解CFA问题的有效性，而且与传统的拉格朗日松弛及子梯度寻优算法相比，解的质量有大幅度提高；与遗传算法相比，对大规模或负荷很重的网络，该算法更具优越性．     

一种改进禁忌搜索的K-medoids聚类算法

针对传统K-medoids聚类算法初始聚类中心随机选择、聚类精度不高、全局搜索能力较差以及禁忌搜索算法对初始值随机选取等问题,提出了一种粒计算与最大距离积法相结合的初始化禁忌搜索初始值算法,将改进后的禁忌搜索算法用来优化K-medoids,以提高聚类算法的性能。通过仿真试验论证了该算法具有较高的效率和准确率以及较强的稳定性。     

大型二维装箱问题及其禁忌算法研究

对大型二维装箱问题进行描述,提出求解该问题的禁忌算法.算法基于自然数编码,设计了货物的摆放规则和序列生成方式,采用二种邻域,根据邻域的不同,构造了两种禁忌表.算法采用惩罚函‘数处理空间利用率约束.介绍算法的原理,给出了具有代表性算例试验结果并且进行了分析.试验结果表明了提出的禁忌算法对优化大型二维装箱问题的有效性.     

一种求解带有阻塞限制的混合流水车间的禁忌搜索算法

针对带有阻塞限制的混合流水车间调度问题,提出一种禁忌搜索算法和优先级规则相结合的方法.开发了启发式调度算法求出问题初始解,应用禁忌搜索算法对工件在第一级的排序进行优化,采用优先级规则进行其他级工件的排序.实验结果表明,该方法大大缩减了搜索空间,能够较好地解决此类调度问题.     

集成生产与预防性维护的流水线车间调度算法

为使机器的可利用率最大化,建立了机器预防性维护的优化周期模型.为同时考虑生产调度与预防性维护调度,以最小Makespan为调度优化目标,提出了一种结合优化预防性维护周期模型的集成启发式调度算法.仿真结果表明,集成启发式算法对流水型车间进行生产与预防性维护调度是有效的和实用的.     

基于改进禁忌搜索算法的立体车库搬运器路径优化建模与仿真

为提升平面移动式立体车库运行效率,通过对搬运器位置转移过程及服务时间进行分析,建立多条件约束的搬运器最短服务时间调度模型,考虑立体车库固定容量下不同层列组合方式及顾客到达率影响因素,提出了一种改进禁忌搜索算法提高搬运器路径搜索速度,设置对照组进行仿真实验,结果表明：6×16的层列组合下算法初始解的服务效率指标最佳;当顾客到达率为12、20 veh/h时,搬运器平均利用率低于50%,相较实例车库搬运器平均服务时间分别减小8.59%、10.29%,当顾客到达率为40、60 veh/h时,搬运器平均服务时间分别减小2.92%、1.5%。可见顾客到达率水平不同,算法适用性不同,在搬运器平均利用率小于50%的情形下算法表现更优,最后以工程项目数据进行验证,证明算法在实际工程中有较强可行性。     

基于遗传禁忌算法的任务分配与调度的研究

任务分配与调度问题是公认的NP问题，为了合理的对备份任务进行分配与调度，使得最短时间内完成备份任务，提出了基于遗传禁忌搜索的备份任务调度算法。重点研究了遗传算法和禁忌搜索算法，并针对二者的不足，提出将其两种算法混合，相互取长补短，仿真实验结果和实例应用表明，笔者提出的算法其搜索效率比单一的遗传算法具有较好的效果。