求解置换Flow shop调度问题的一种启发式算法

提出了一种新的求解置换flowshop调度问题的启发式算法。问题的目标是:在满足约束条件的前提下使得调度的makespan尽可能地小。定义了一种新的邻域结构。给出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向。计算了一组著名的问题实例。计算结果表明,算法的优度高于一种改进的遗传算法。     

求解Job Shop调度问题的一种新的邻域搜索算法

利用了混合邻域结构进行搜索来求解Job Shop调度问题．算法使用的混合邻域结构不仅使邻域搜索具有效率,而且有助于搜索有效地跳出局部极小值的陷阱,让计算走向前景更好的区域．算法采用的“单机调度”和“同工件工序调整”的跳坑策略能够帮助搜索找到更好的局部极小值．采用国际文献中所有的10工件10机器算例以及另外7个难算例作为本算法的测试实验集,与目前国际上最好的近似算法和另外一种先进算法进行了比较．实算结果验证了算法的寻优性能．     

面向柔性作业车间调度问题的改进变邻域搜索算法

针对柔性作业车间调度问题的特点,提出一种求解该问题的改进变邻域搜索算法。结合问题特点设计合理的编码方式,采用遗传算法进行最优解搜索,将搜索的结果作为变邻域搜索算法的初始解,以提高初始解的质量。为提高局部搜索能力,设计3种不同的邻域结构,构建邻域结构集以产生邻域解,保证邻域解的搜索过程中解的可行性以提高求解效率。针对一系列典型的柔性作业车间调度问题的实例,运用所设计的改进变邻域搜索算法进行测试求解,并将计算结果与文献中其他算法的测试结果进行比较,验证了所提出方法求解柔性作业车间调度问题的可行性和有效性。     

一种求解车间作业调度问题的混合邻域结构搜索算法

车间作业调度问题是优化组合中一个著名的难题,问题的目标是在满足约束条件的前提下,使调度的加工周期尽可能小。文章中提出了利用新的混合邻域结构进行搜索来求解车间作业调度问题。对于算法关键的邻域构造问题以及跳坑策略给出了提高算法优度的解决方案。采用43个不同规模和难度的国际标准算例做为本算法的测试实验集,39个算例找到了最优解,其中包括著名的难例FT10。与当前国外学者提出的一种先进算法进行了比较,算法的优度高于被比较的先进算法。     

一类基于FSP问题Block性质的快速TS算法

为解决现有算法在求解大规模流水线调度问题（FSP）时计算时间过长的问题,从缩小邻域的角度出发,提出一种基于FSP问题Block性质的快速禁忌搜索（TS）算法．利用Block性质．算法在保证不丢失最优解的基础上．将邻域中大部分劣解排除．将搜索重点集中在邻域中“最优希望”的区域,以缩小邻域和减少计算时闻．数值仿真实验表明,该算法能在较短时间内获得大规模FSP问题的满意解．     

带准备时间的单机调度问题的混合进化算法研究

提出了一种混合进化算法（HEA）用于求解具有序列相关依赖且带准备时间的单机调度问题, 其优化目标为最小化总延迟。该混合进化算法由局部搜索和进化算法框架混合而成。HEA具有一些新的特点, 例如在局部搜索中采用了一种新提出的基于块移动的邻域结构, 这种邻域结构合理地限制了搜索空间, 提高了算法的搜索效率; 在HEA中采用了一种新的组合算子——块顺序交叉算符（BOX）来产生新的子代工作序列。用本算法对当前国际文献中公开的两组共64个算例进行了测试, HEA改进了9个算例在当前文献中的最优解, 表明了所提出的HEA算法的优越性。与之前的国际文献中最好的四个启发式算法进行了详细比较, 表明了HEA算法的优势。     

求解Job Shop调度问题的混合蚁群算法研究

为了解决单一算法求解Job Shop调度问题存在的不足，该文提出了一种混合算法，将蚁群算法用于全局搜索。针对蚁群算法易于陷入局部最优的情况，提出了一种基于关键工序的邻域搜索方法，将使用此邻域搜索方法的TS算法作为局部搜索策略。利用TS算法较强的局部搜索能力，提高了蚁群算法的优化能力，达到改善Job Shop调度问题解的质量。实验结果表明，混合算法在较短的时间内，找到了FT10、LA24、LA36等典型benchmarks问题的最优解，得到的makespan的平均值较并行遗传算法(PGA)和TSAB算法均有所提高。     

新颖的阻塞流水车间调度量子差分进化算法

针对阻塞流水车间调度问题(BFSP),提出了一种新颖的量子差分进化(NQDE)算法,用于最小化最大完工时间。该算法将量子进化算法(QEA)与差分进化(DE)相结合,设计一种新颖的量子旋转机制控制种群进化方向,增强种群多样性;采用高效的基于变邻域搜索的量子进化算法(QEA-VNS)协同进化策略增强算法的全局搜索能力,进一步提高解的质量。基于Taillard's benchmark实例仿真,结果表明,所提算法在最优解数量上明显高于目前较好的启发式算法--INEH,改进了110个实例中64个实例的当前最优解;在性能上也优于目前有效的元启发式算法--新型蛙跳算法(NMSFLA)和混合量子差分进化(HQDE),产生最优解的平均百分比偏差(ARPD)均下降约6%。NQDE算法适合大规模阻塞流水车间调度问题。     

基于分布估计算法的二阶段置换流水车间调度算法*

针对以完工时间最小化为目标的置换流水车间调度问题（PFSP）,提出了一种基于分布估计算法的二阶段置换流水车间调度算法。首先,在算法的第一阶段采用分布估计算法对PFSP进行优化得到一个局部最优解;为了进一步提高解的优化质量,在第二阶段提出了一种新的混合邻域搜索机制对第一阶段获得的局优解进行邻域搜索;最后,对Rec类和Tai类基准测试问题进行了测试,实验结果证实了算法的有效性。     

一种求解二维矩形Packing问题的拟人型全局优化算法

针对二维矩形Packing问题,提出了基于占角动作的基本算法。以基本算法为基础,提出了三阶段优化的拟人型全局优化算法。在第一阶段生成初始布局。在第二阶段交替调用邻域搜索子程序和跳坑策略子程序对矩形块的优先级排序进行优化。邻域搜索采用交换式和插入式两种邻域结构,避免单一邻域结构的局限性。当搜索遇到局部最优解时,采用跳坑策略子程序跳出局部最优解,将搜索引向有希望的区域。在第三阶段调用优美度枚举子程序对占角动作的选择作进一步优化。提出了两条优度定理。对于六组benchmark测试用例的实验结果表明,算法的整体表现优于当前文献中的先进算法。针对矩形块方向固定的情形,算法对zdf6和zdf7两个问题实例得到了比已有文献记录更优的布局。     

An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling

This paper presents a local search, based on a new neighborhood for the job‐shop scheduling problem, and its application within a biased random‐key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based on an extension of the 1956 graphical method of Akers, is applied to improve the solution. The new heuristic is tested on a set of 205 standard instances taken from the job‐shop scheduling literature and compared with results obtained by other approaches. The new algorithm improved the best‐known solution values for 57 instances.     

求解柔性作业车间调度问题的新型改进Jaya算法

为有效解决复杂的柔性作业车间调度问题,以最小化最大完成时间为目标,提出了一种结合了变邻域搜索算法的新型改进Jaya算法来求解。为不断挖掘和优化探索最优解,提高算法求解的结果质量,通过Jaya算法的原理重新提出一种解的更新机制,此外在Jaya算法原理的基础上嵌入一种变邻域搜索策略,并在传统邻域结构的基础上重新设计了两种新型邻域结构,扩大了邻域搜索范围,增强了Jaya算法的局部搜索能力,避免算法因失去解的多样性从而陷入局部最优。运用基准算例对该算法的求解性能进行了验证,并与其他算法的仿真结果进行对比,结果表明该改进算法的求解效率更高。     

改进的基于分解的多目标进化算法求解双目标模糊柔性作业车间调度问题

针对同时考虑最大模糊完工时间和总模糊机器负载的双目标模糊柔性作业车间调度问题(BFFJSP),本文提出了一种改进的基于分解的多目标进化算法(IMOEA/D),同时最优化最大模糊完工时间和总模糊机器负载,其主要特点是:1)采用3种初始化种群的策略; 2)提出了非支配解优先策略; 3)设计了结合5种局部搜索策略的变邻域搜索; 4)提出了计数器策略预防陷入局部解.运用大量实例进行了算法策略分析和对比实验,仿真结果表明, IMOEA/D在求解BFFJSP上具有更优性能.     

Scheduling of no buffer job shop cells with blocking constraints and automated guided vehicles

The blocking job shop (BJS) problem is an extension of a job shop problem with no buffer constraints. It means that after a job is completed on the current machine, it remains on that machine until the next machine becomes available. This paper addresses an extension of the BJS problem, which takes into account transferring jobs between different machines using a limited number of automated guided vehicles (AGV), called a BJS–AGV problem. Two integer non-linear programming (INLP) models are proposed. A two-stage heuristic algorithm that combines an improving timetabling method and a local search is proposed to solve the BJS–AGV problem. A neighborhood structure in the local search is proposed based on a disjunctive graph model. According to the characteristics of the BJS–AGV problem, four principles are proposed to guarantee the feasibility of the search neighborhood. Computation results are presented for a set of benchmarking tests, some of which are enlarged by transportation times between different machines. The numerical results show the effectiveness of the proposed two-stage algorithm.     

求解低碳调度问题的改进型候鸟优化算法

针对柔性作业车间,建立一种以能耗最小化为目标的数学模型,解决低碳策略下的该车间内的作业调度问题。对于上述模型,提出一种改进型候鸟优化（Improved Migrating Birds Optimization,IMBO）算法进行求解。结合全局搜索、局部搜索和随机规则三种方式初始化种群,确保算法的求解质量和收敛速度。采用两种有效的邻域结构构造个体的邻域解,并在此基础上设计一种局部搜索方法增强算法的局部寻优能力。此外,引入一种跳跃机制避免算法陷入早熟收敛状态。通过大量计算结果验证了模型和算法的可行性和有效性。     

A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem

Tabu search (TS) algorithms are among the most effective approaches for solving the job shop scheduling problem (JSP) which is one of the most difficult NP-complete problems. However, neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of the tabu search for the JSP. In this paper, a new enhanced neighborhood structure is proposed and applied to solving the job shop scheduling problem by TS approach. Using this new neighborhood structure combined with the appropriate move evaluation strategy and parameters, we tested the TS approach on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our approach dominates all others in terms of both solution quality and performance.     

求解柔性作业车间调度的GATOC混合方法

柔性作业车间调度问题是经典作业车间调度问题的扩展,它允许工序在可选加工机器集中任意一台上加工,加工时间随加工机器不同而不同。针对柔性作业车间调度问题的特点,提出一种基于约束理论的局部搜索方法,对关键路径上的机器的负荷率进行比较,寻找瓶颈机器,以保证各机器之间的负荷平衡。为了克服传统遗传算法早熟和收敛慢的缺点,设计多种变异操作,增加种群多样性。为了更好保留每代中的优良解,设计了基于海明距离的精英解保留策略。运用提出的算法求解基准测试问题,验证了算法的可行性和有效性。     

基于改进迭代贪婪算法的预制构件调度研究

迭代贪婪算法是一种具有较强局部搜索能力的元启发式算法,但由于传统迭代贪婪算法搜索范围过大,搜索效率有限,为了进一步提升传统迭代贪婪算法的搜索能力,考虑到阈值接受算法具有能缩小搜索范围的特点,提出了一种改进的迭代贪婪算法解决流水车间预制生产的订单接受与调度问题。该改进算法是在破坏原调度序列后加入一种基于构造启发式规则的重建策略,并结合阈值接受算法的自适应接受准则用以跳出局部最优。经大量仿真实验结果显示,与传统迭代贪婪算法、禁忌搜索算法以及遗传算法对比,改进的迭代贪婪算法具有更好的求解质量和鲁棒性。     

Greedy randomized adaptive search for dynamic flexible job-shop scheduling

Dynamic flexible job shop scheduling problem is studied under the events such as new order arrivals, changes in due dates, machine breakdowns, order cancellations, and appearance of urgent orders. This paper presents a constructive algorithm which can solve FJSP and DFJSP with machine capacity constraints and sequence-dependent setup times, and employs greedy randomized adaptive search procedure (GRASP). Besides, Order Review Release (ORR) mechanism and order acceptance/rejection decisions are also incorporated into the proposed method in order to adjust capacity execution considering customer due date requirements. The lexicographic method is utilized to assess the objectives: schedule instability, makespan, mean tardiness and mean flow time. A group of experiments is also carried out in order to verify the suitability of the GRASP in solving the flexible job shop scheduling problem. Benchmark problems are formed for different problem scales with dynamic events. The event-driven rescheduling strategy is also compared with periodical rescheduling strategy. Results of the extensive computational experiment presents that proposed approach is very effective and can provide reasonable schedules under event-driven and periodic scheduling scenarios.