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

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

求解置换流水车间调度问题的布谷鸟算法

分析了布谷鸟算法的优化机理和特点,针对最小化最大完工时间的置换流水车间调度问题,采用基于最小位置值规则的随机键编码方式,应用布谷鸟算法进行求解.通过选取的标准算例对算法进行了仿真测试,并与萤火虫算法和粒子群算法进行对比,测试结果表明了该算法求解置换流水车间调度问题的有效性和优越性.该方法可作为解决流水线生产调度问题的一种有效方法.     

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

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

强制工期相等的双机流水车间排序问题

讨论了强制工期相等的n个工件在双机流水车间的加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会不可行排序.先讨论问题的可行性,如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后,给出一个多项式时间算法,在预排序列的基础上,通过调整最先加工的工件来获得最优排序.     

任务无准备时间最小化加权最大延误单机调度问题的若干结果

研究任务无准备时间最小化加权最大延误的单机调度问题,给出逆向最小带权延误排序法并证明其最优性.随后,引入延误差函数概念,借助它给出简化的基于延误差函数的排序算法.特别地,对于工期相同的情形,给出更简便的权值关于期限正态分布算法.最后,借助实例说明了上述算法的应用.     

求解作业车间调度问题的改进飞蛾扑火优化算法

针对作业车间调度问题,为了克服早熟收敛和容易陷入局部最优等不足,提出一种基于Lévy飞行的改进飞蛾扑火优化模型(LMFO)。首先,采用MFO算法求解作业车间调度问题,并与粒子群算法(PSO)、遗传算法(GA)进行对比研究,证明了MFO算法求解此类问题的有效性;然后,采用改进的随机键编码,引入Lévy飞行对MFO算法进行改进;最后,仿真实验表明,LMFO算法在求解作业车间调度问题时优于MFO、PSO和GA算法,能够跳出局部最优找到更好的解,且具有一定的鲁棒性。     

加工时间为线性增函数有上界的排序问题

本文讨论工件的加工时间是其开工时间的一类线性增加函数有上界的单机排序问题1|pj(t)(t0,T1,T2)|Cmax:设工件集J=J1,J2,…,Jn中的每个工件需要在一台机器上得到加工;工件集J被划分成两组J=Ω1+Ω2;机器上第一个被加工的工件在时刻t00开始加工;Ω1中工件的加工时间为pj(t)=ajt(当tT1)或pj(t)=ajT1(当t≥T1),Ω2中工件的加工时间为pj(t)=ajt(当tT2)或pj(t)=ajT2(当t≥T2),其中T2T1t0均是给定的常数,t表示对应工件的开工时刻;排序的目的是极小化时间表长(最大完工时间)Cm ax。在所得的引理2和引理3的基础上,本文给出一个复杂度为nlogn的多项式时间算法,从而也证明了所讨论的问题是多项式时间可解得的。     

带有学习效应的多目标置换流水车间调度问题研究

在综合考虑经济指标和环境因素的基础上,提出了以最小化最大完工时间和总能耗为优化目标的置换流水车间调度问题,并着重考虑学习效应对该问题的影响。针对该问题的特点,构建了带有学习效应的多目标置换流水车间调度模型,并设计了一种嵌有批量处理和扰动算子操作的混合蛙跳算法对模型进行求解。利用扩展的标准测试问题验证了该算法的性能,并与非支配排序遗传算法、强帕累托进化算法进行了对比分析,实验结果表明改进的混合蛙跳算法具有较好的寻优能力。利用此算法得到了不同学习率下的优化目标值,并运用敏感性分析探讨了学习效应对优化目标的影响程度,从而为企业制定合理的生产调度方案提供参考。     

面向作业车间调度问题的改进型蝙蝠算法

针对作业车间调度问题(Job shop scheduling problem,JSP),提出了一种改进型蝙蝠算法(Improved bat algorithm,IBA)以优化车间内工件的最大完工时间.根据作业车间调度问题的特点以及基本蝙蝠算法的搜索机制,首先对个体位置向量进行了设计,实现了蝙蝠算法中离散问题的连续编码;然后分别采用GT算法和随机生成两种方法对算法种群进行初始化,以提高初始解的质量.此外,采用三种邻域结构,并在此基础上设计了变邻域搜索策略作用于最优个体,以避免算法出现早熟收敛,提高IBA算法的性能.最后,针对JSP问题的基准算例进行了大量的仿真实验,计算结果验证了本文所提出的IBA算法的可行性和有效性.     

目标函数是最大延误的数学期望的单机随机调度问题

在任务的加工时间和工期是相互独立的随机变量的情况下研究单机随机排序问题,目标函数为最大延误的数学期望。通过理论分析,给出了该问题的不可中断静态优先策略,并通过实例验证。     

有分离调整和移走时间的两机器流水作业最大延误问题

在工件的调整时间和移走时间独立于加工时间的两机器流水作业问题中，同一工件的“调整”步及“移走”步在两台机器上可重叠进行，但“加工”步不能重叠，本以最大延误为目标函数讨论问题的解中工件排列应满足的条件，根据这些条件我们构作了两个近似算法。     

序列相关Setup单机调度的最小化最大拖期分枝定界算法

研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.     

寻找最大独立集的算法

提出两种基于贪婪思想的局部搜索算法寻找给定图的最大独立集,通过测试第二种算法在图密度小时更优与第一种算法.由于局部搜索算法的缺陷,修改邻域函数与顶点的选择是进一步研究的问题;考虑到算法的有效性,时间复杂度和近似算法的比较也是值得进一步研究的方向.     

用GA算法解不确定条件下Job Shop的提前/拖期调度问题

研究了具有公共交货期窗口的 Job Shop的提前 /拖期调度问题 ,并考虑了处理时间的不确定性 ,采用三角模糊数表示不确定性信息 ,提出了基于遗传算法的优化方法并以仿真实验验证了算法的有效性     

一种启发式的分布式最大独立集算法

从最大独立集问题的0-1整数规划数学描述入手,首先针对树图情形提出了一种基本的分布式树（Tree）算法,并证明该算法在树图情形下是最优的,然后将该Tree算法针对一般图情形进行了启发式的修正,得到一种新的分布式修正树（m-Tree）算法.理论分析表明,当图为树或二分图时,m-Tree算法可以简化为基于信用传播（BP）的分布式算法,是对BP算法的一种推广.仿真结果表明,对于树或二分图情形,m-Tree算法与BP算法都能收敛至最优解;对于一般图情形,m-Tree算法的收敛性能与权和性能均远优于BP算法,并且其权和性能接近最优解.     

A Heuristic for Two-Stage No-Wait Hybrid Flowshop Scheduling with a Single Machine in Either Stage

This paper studies the hybrid flow-shop scheduling problem with no-wait restrictions. The production process consists of two machine canters, one has a single machine and the other has more than one parallel machine. A greedy heuristic named least deviation algorithm is designed and its worst case performance is analyzed. Computational results are also given to show the algorithm‘s average performance compared with some other algorithms. The least deviation algorithm outperforms the others in most cases tested here, and it is of low computational complexity and is easy to carry out,thus it is of favorable application value.     

单机分批加工最大迟后问题的一个快速算法

本文考虑了下述单机分批加工问题，在时刻零同到达的ｎ个工件需分成若干批在同台机器上加工，同批中的工件相邻，任一工件的完工时间为所在批中全部工件完工时间的，机器每加工一批工件需一相同的调整时间，文中以工件的最大迟后为目标函数，对上述分别问题用动态规划技术给出了一多项式时间算法。     

平行批排序最小化最大完工时间在线算法的一个注记

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,NavalResearch Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algo-rithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为(5 1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1 α)r αp时刻以后加工,其中α=(5-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.