混合遗传算法求解带不相关并行机的HFSSP

研究了带不相关并行机和批生产约束的混合流水车间调度问题,其中初始阶段为串行批处理机,相邻加工阶段间工件的运输时间独立于加工时间。针对该问题,以最小化最大完工时间(makespan)为目标,建立了整数规划模型,提出一种结合NEH启发式算法、局域搜索和自适应遗传算法的混合遗传算法获取近优解。采用NEH启发式算法产生初始工件加工序列群以提高群质量,提出自适应参数调节机制设计交叉变异概率,进而利用交叉和变异操作改进解的质量。最后,通过局域搜索产生邻域解以更新遗传算法(GA)的解。仿真实验测试了不同规模的实例,与其他基于GA的混合算法的性能进行对比,结果表明所提出的混合遗传算法优于其他算法,能在合理的计算时间内得到较好的近优解。     

带不相关并行机和有限缓冲MHFS调度的混合启发式算法

研究每阶段含不相关并行机的多阶段混合流水车间问题(MHFSP),工件的加工时间取决于所分配的机器,相邻阶段之间缓冲区能力有限.鉴于直接求解该NP-hard问题较为困难,将其转化为带阻塞和不相关并行机的MHFSP (BMHFSP-UPM),建立整数规划模型,基于遗传算法(GA)和禁忌搜索(TS)提出一种混合启发式算法(HHGA&TS)进行求解.在该算法中,设计基于多阶段并行加工的二维矩阵编码方案,继而基于二维矩阵元胞组的初始解群体表述设计参数自适应策略;引入基于工件位-基因位的单点倒置交叉以及基于机器号的单点变异过程,利用GA求解机制完成解更新过程;设计机器号次序交换(MNE)、工件位置交换(JNE)、工件工序变异(JNM)三种邻域解移动规则,从而完成基于MNE-JNE-JNM的TS二次优化.仿真实验测试了多达120个工件的720组不同规模实例,结果表明,相较于GA、TS及NEH-IGA,所提出的混合启发式算法在解的质量方面表现更佳.     

多构造蚁群优化求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种多构造蚁群优化求解算法。在该算法中,蚁群采用两种方式构造解,分别是基于NEH(Nawaz-Enscore-Ham,NEH)启发式算法和Rajendran启发式算法,并根据解的质量,自适应地调整两种构造方式在蚁群中所占的比例。对置换流水车间调度问题的基准问题测试表明,提出的算法是有效的。     

基于改进离散和声算法的批量流水线调度研究

针对批量流水线调度问题,提出了以总流经时间为目标的改进离散和声算法。与基本的和声算法相比,该算法首先采用了基于工件序列的编码方式,使其直接应用于调度问题,同时运用NEH和SWAP方法产生初始和声库,保证了初始种群具有较高的质量和多样性。使用自适应和声微调概率参数和INSERT方法产生新解,提高了算法的优化性能。为了提高算法的局部搜索能力,结合交换扰动策略和插入邻域搜索算法给出了两种混合求解策略。仿真实验表明所提算法的有效性。     

求解置换流水车间调度问题的改进遗传算法

针对置换流水车间调度问题的基本特征和传统遗传算法易早熟的缺陷,设计了改进遗传算法来求解此问题。采用NEH和Palmer启发式算法进行种群初始化,以提高初始解的质量;根据Metropolis准则对染色体进行选择操作,避免陷入局部最优;在变异过程中引入禁忌算法,避免迂回搜索;在算法迭代过程中引入了保优机制,避免丢失优秀染色体的基因信息;采用自适应终止准则,以保证解的质量。基于典型Benchmark算例的仿真实验结果表明,算法在求解质量和收敛速度方面明显优于NEH算法和种群经过初始优化的传统遗传算法。     

改进的蚁群算法求解置换流水车间调度问题

针对蚂蚁算法在求解置换流水车间调度问题时易陷入局部最优以及计算时间较长的缺点,对最大最小蚂蚁系统(MMAS)进行了改进。在该算法中,采用NEH启发式算法提高初始解质量,并通过自适应的调节策略进一步提高蚁群算法的搜索能力。运用提出的混合算法求解Taillard基准测试集,并将测试结果与其他算法进行比较,验证了该调度算法的有效性。     

禁忌搜索算法解决零空闲流水线调度问题

针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型.新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能.利用动态方式更新禁忌表长,提高了新算法的鲁棒性.为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法.仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值.     

含忽略工序和不相关机的混合流水车间调度

研究从炼钢等生产过程提炼出的含忽略工序和不相关并行机的混合流水车间调度问题,以最小化最大完工时间为目标,建立整数规划模型,并提出结合全局搜索、自适应遗传算法和候鸟优化的遗传候鸟优化算法以求解该模型。在算法中采用与处理时间相关的全局搜索和随机程序以获得初始种群,提出自适应交叉和变异操作改进遗传算法解,在迭代进程中,引入基于工件、机器和工序位3种邻域搜索结构的候鸟优化算法更新最佳解。仿真实验中将遗传候鸟优化算法的实验结果与几种启发式算法进行对比,证明了模型和算法的有效性。     

基于自适应遗传算法的侦察资源优化

提出基于地理信息系统的侦察资源优化模型,在地形分析结果基础上利用自适应遗传算法进行求解.算法采用多参数映射编码,通过启发式初始化方法和专门的遗传算子保证初始个体的有效,此外交叉概率和遗传概率的适应性策略,可以确保适应度函数对算法进化的正确引导.仿真结果证明该方法对侦察资源优化具有一定参考价值.     

混合遗传NEH算法在流水车间调度中的应用

针对流水车间调度问题提出一种混合遗传NEH算法,以提高求解效率.NEH算法是一种高效的构造性算法具有很强的邻域搜索能力,而遗传算法则能有效地提供全局搜索.据此,新算法首先通过选择、交叉和变异操作,经过迭代获得一个较好解,然后在这个解所在的特定邻域内进行改进的NEH搜索,以获得更好解,经过NEH搜索后求得的最好解作为一个新个体加入下一代种群中,继续进行遗传操作.通过对流水车间调度的最小化最大完成时间问题的仿真实验结果表明,新算法有明显改进.     

SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM

In this article, a hybrid metaheuristic method for solving the open shop scheduling problem (OSSP) is proposed. The optimization criterion is the minimization of makespan and the solution method consists of four components: a randomized initial population generation, a heuristic solution included in the initial population acquired by a Nawaz-Enscore-Ham (NEH)-based heuristic for the flow shop scheduling problem, and two interconnected metaheuristic algorithms: a variable neighborhood search and a genetic algorithm. To our knowledge, this is the first hybrid application of genetic algorithm (GA) and variable neighborhood search (VNS) for the open shop scheduling problem. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches a high quality solution in short computational times. Moreover, 12 new hard, large-scale open shop benchmark instances are proposed that simulate realistic industrial cases.     

A robust genetic algorithm for scheduling realistic hybrid flexible flow line problems

This article addresses the problem of hybrid flexible flow line where some constraints are considered to alleviate the chasm between the real-world industries scheduling and the production scheduling theories. Sequence-dependent setup times, machine release date and time lags are three constraints deemed to project the circumstances commonly found in real-world industries. To tackle the complexity of the problem at hand, we propose an approach base on genetic algorithm (GA). However, the performance of most evolutionary algorithms is significantly impressed by the values determined for the miscellaneous parameters which these algorithms possess. Hence, response surface methodology is applied to set the parameters of GA and to estimate the proper values of GA parameters in continually intervals. Finally, problems of various sizes are utilized to test the performance of the proposed algorithm and to compare it with some existing heuristic in the literature such as SPT, LPT and NEH.     

自动化码头考虑缓冲区的设备协调调度优化

为研究自动化码头缓冲区的设置对装卸设备作业协调性的影响,针对“双小车岸桥+AGV+缓冲支架+自动化轨道吊”的装卸工艺,利用缓冲有限的柔性流水车间调度理论建立集成调度优化模型,设计了以NEH启发式算法产生初始解的遗传算法对模型进行求解,得出相应的设备调度优化方案与完工时间,并通过对比遗传算法与粒子群算法的运算结果验证了提出的模型与算法的有效性,进而分析了不同缓存区容量对完工时间以及设备使用率的影响。结果表明,设置缓冲区能有效提高不同设备之间的作业协调性,显著减少AGV的使用数量与作业完工时间。     

差异工件流水车间批调度问题的求解

针对流水车间批调度问题,提出一种基于群智能算法的求解思路。结合问题具体特点,给出工件集合的分批策略,设计了将Palmer和Best Fit（BF）分批规则相结合的分批方法;在批排序阶段,提出了一种改进的微粒群算法;在粒子初始生成阶段,通过引入NEH启发式算法改进了粒子的初始化质量;在全局最佳位置更新前,通过变邻域搜索优化了算法的局部搜索能力,避免了算法陷入局部最优。仿真实验表明,改进后的算法优于传统的微粒群算法和NEH启发式算法。     

An artificial neural network based heuristic for flow shop scheduling problems

The objective of this paper is to find a sequence of jobs in the flow shop to minimize makespan. A feed forward back propagation neural network is used to solve the problem. The network is trained with the optimal sequences of completely enumerated five, six and seven jobs, ten machine problem and this trained network is then used to solve the problem with greater number of jobs. The sequence obtained using artificial neural network (ANN) is given as the initial sequence to a heuristic proposed by Suliman and also to genetic algorithm (GA) as one of the sequences of the population for further improvement. The approaches are referred as ANN-Suliman heuristic and ANN-GA heuristic respectively. Makespan of the sequences obtained by these heuristics are compared with the makespan of the sequences obtained using the heuristic proposed by Nawaz, Enscore and Ham (NEH) and Suliman Heuristic initialized with Campbell Dudek and Smith (CDS) heuristic called as CDS-Suliman approach. It is found that the ANN-GA and ANN-Suliman heuristic approaches perform better than NEH and CDS-Suliman heuristics for the problems considered.     

一种用于PFSP节能优化的混合禁忌搜索算法

为了追求节能减排与净利润最大化,建立一种置换流水车间订单接受与调度模型。禁忌搜索是一类启发式全局搜索算法,传统禁忌搜索对初始解依赖较大,没有对考虑能效的置换流水车间调度问题进行更深入的优化。鉴于问题的复杂性,提出了一种节能混合禁忌搜索算法,结合了NEH构造启发式算法的优势,并在该算法中设计了订单接受与拒绝编码方式、能耗调整与交货期配置策略。最后采用大量随机实例对性能进行分析。实验结果表明,通过上述改进,改善了算法的全局搜索能力与解决复杂模型的寻优能力,节能混合禁忌搜索较单一算法而言性能更优,可以有效增加企业总净利润,降低能源消耗。     

抑制孤立簇的软件模块化优化算法

针对传统软件模块化指标在解决软件模块化问题时容易导致孤立簇的问题,提出改进型软件模块化指标IMQ作为进化算法的适应函数以有效抑制孤立簇现象,并以IMQ最大化为目标建立软件模块化的数学规划模型,设计符合问题特点的基于相似度竞争和选择机制的改进遗传算法（IGA）求解该模型。首先,运用边收缩方法的启发式策略生成高质量的初始解,并将其作为种子植入到初始种群中;然后,利用IGA对模型进行求解,在提升搜索效率的同时进一步提高解的质量;最后,运用真实数据和仿真数据进行对比实验。实验结果表明IMQ指标能有效减少孤立簇的数目,而IGA比传统的多点爬山算法（IHC）和基于分组编码（GNE）的遗传算法具有更强的寻优能力和鲁棒性。