求解模糊Job Shop调度的遗传算法与蚁群算法融合研究

提出一种算法融合策略,解决单一算法求解模糊Job Shop调度问题存在的不足,提高这类问题的求解质量.算法融合策略中,采用遗传算法和蚁群算法进行并行搜索;根据模糊Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法和蚁群算法的局部搜索能力.采用算法融合策略的混合优化算法对以13个难的benchmarks问题经模糊化得到实例进行求解,在较短的时间内,得到的平均满意度较并行遗传算法(PGA)提高5.24%、较TSAB算法提高8.40% .采用算法融合策略构造的混合算法具有较强的搜索能力,说明提出的混合搜索策略是有效的.     

模糊Job Shop调度中的混合搜索策略的研究

采用并行遗传算法作为全局搜索算法，提出一种混合搜索策略，用于求解模糊Job Shop调度问题．根据模糊Job Shop调度问题解的特征，提出基于关键工序的邻域选择方法，并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法，加强了遗传算法局部搜索能力．针对13个困难benchmark问题的实验结果表明，在较短的时间内，混合搜索策略的算法得到的平均满意度比并行遗传算法提高4.67%，比TSAB算法提高5.76%．采用的禁忌搜索算法改善了遗传算法的局部搜索能力，说明提出的混合搜索策略是有效的．     

求解作业车间调度问题的混合帝国主义竞争算法

针对最小化最大完工时间的作业车间调度问题（JSP）,提出一种结合帝国主义竞争算法（ICA）和禁忌搜索（TS）算法的混合算法。混合算法以帝国主义竞争算法为基础,在同化操作中融入遗传算法中的杂交算子和变异算子,使算法全局搜索能力更强。为了克服帝国主义竞争算法局部搜索能力弱的缺点,引入禁忌搜索算法进一步优化同化操作后的后代。禁忌搜索算法采用混合邻域结构和新型选择策略,使得算法能够更有效地搜索邻域解。混合算法兼具全局搜索能力和局部搜索能力,通过对13个经典的Benchmark调度问题进行仿真测试,并与近年4种新型混合算法进行对比分析,实验结果表明了所提算法求解Job Shop调度问题的有效性和稳定性。     

约束满足混合算法求解提前/拖期Job Shop调度问题

针对提前/拖期Job Shop调度问题,建立其约束满足优化问题模型,提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想,通过约束传播技术和启发式修复算法,得到可行调度作为禁忌搜索算法的初始解;再进行关键路径上的邻域变换,优化当前解;并采用一种全局邻域交换策略,扩大搜索空间,改善优化结果。数据实验表明了该混合算法的可行性和有效性。     

基于蚁群算法的车间作业调度问题研究

对基于蚁群算法的车间作业调度问题求解进行了研究,在分析了传统蚁群算法求解车间作业调度问题容易出现早熟、收敛于局部最优解以及搜索速度慢的缺陷,提出了一种改进的混合蚁群算法。该方法在信息素更新规则上利用信息素局部更新策略和全局更新策略来进行信息素的更新,并将领域搜索与蚁群算法相结合,从而求得问题的可行解。最后,基于benchmarks问题进行了实验仿真,实验结果证明该改进混合算法的有效性及可行性。     

基于结点群的高效的动态二分查找器

针对求解NP-hard的车间生产调度存在的问题,提出了一种基于思维进化的蚁群算法。该算法建立在传统蚁群算法上,并结合思维进化思想和局部寻优思想克服了基本蚁群算法易陷入局部最优的缺陷,改进了状态转移规则,限定了信息素的范围,改进了信息素更新策略,并增加了邻域搜索。实验表明,对于典型生产调度问题,基于思维进化的蚁群算法可以求得理论最优解,在最优解、最差解和平均解3个指标上都优于基本蚁群算法,体现出了较好的性能。     

基于混合蚁群算法的网格任务调度

针对网格任务调度的调度时间长、资源负载不平衡等问题,提出一种基于混合蚁群算法的网格任务调度方法。该方法将禁忌搜索作为蚁群算法的局部搜索策略,以扩大解的搜索空间,避免陷入局部最优,并通过多样化机制提高算法收敛速度。利用平衡因子调节信息素的更新,改善资源的负载平衡性能。     

基于邻域搜索的改进最大最小蚁群算法

针对蚁群算法求解旅行商问题时易陷入局部最优的问题,提出一个改进的混合最大最小蚁群算法,并应用于求解旅行商问题.上述算法设计了一种新的信息素更新模型,单个蚂蚁每走一步就进行信息素局部更新,在所有的蚂蚁搜索一周后,最优路径蚂蚁进行全局信息素更新.提出一种新的邻域搜索模型,将邻域大小设置为原来的一半,提高了计算的效率.在每个蚂蚁的一个周期循环后,使用邻域搜索算法优化最优解的路径长度.仿真结果表明,改进算法具有较高的求解精度和收敛速度.     

强化Dynasearch & TS算法求解酸轧生产调度问题

酸轧生产调度的主要任务是在满足酸轧机组生产工艺和能力约束下, 考虑下游机组的流向需求,为保证生产连续性和平滑过渡的要求,从给定候选池中选择适合的板卷构成一个酸轧调度单元. 针对此问题, 本文建立了以最小化过渡费用和调度单元剩余容量惩罚费用为目标的整数规划模型, 提出了一种嵌入强化Dynasearch算法的禁忌搜索混合算法. 该混合算法采用基于最小插入法的两阶段启发式产生初始解, 根据采用邻域结构的不同设计双禁忌表, 为了避免算法陷入局部最优, 在禁忌搜索的每次迭代过程中嵌入Swap邻域和Inner-insert邻域相结合的多交换Dynasearch邻域, 并设计了多项式动态规划算法搜索该邻域. 针对问题的特征, 提出了Block分区结构, 基于此分析了多个可行解性质, 有效降低了搜索空间. 与一般禁忌搜索算法比较, 结果表明所提出的强化Dynsearch TS (Tabu search)算法求解效果明显优于一般TS算法, 平均改进量为3.62%, 算法运行时间大大缩短. 验证了该算法在解决此类问题的有效性.     

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

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

Group shops scheduling with makespan criterion subject to random release dates and processing times

This paper deals with a stochastic group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the other shop scheduling problems such as the flow shop, the job shop and the open shop scheduling problems. Both the release date of each job and the processing time of each job on each machine are random variables with known distributions. The objective is to find a job schedule which minimizes the expected makespan. First, the problem is formulated in a form of stochastic programming and then a lower bound on the expected makespan is proposed which may be used as a measure for evaluating the performance of a solution without simulating. To solve the stochastic problem efficiently, a simulation optimization approach is developed that is a hybrid of an ant colony optimization algorithm and a heuristic algorithm to generate good solutions and a discrete event simulation model to evaluate the expected makespan. The proposed approach is tested on instances where the random variables are normally, exponentially or uniformly distributed and gives promising results.     

基于混合人工蜂群算法的多目标柔性作业车间调度问题研究

传统的优化算法在求解面对多目标柔性作业车间调度时,往往求解效率低且难以获得最优解。为了求解多目标柔性作业车间调度问题,设计了混合人工蜂群算法。种群的初始化采用了多种方法相结合的策略。在人工蜂群算法的不同阶段采用不同的搜索机制,在雇佣蜂阶段采用开发搜索,针对跟随蜂阶段蜜蜂跟随的对象的优秀解进行小幅度的更新,从而提高了搜索的表现。禁忌搜索与改进的人工蜂群算法相结合,有效的提升了获得最优解的概率。通过相关文献中的标准实例对设计的混合人工蜂群算法进行一系列求解测试,实验的结果有效的说明了算法在求解柔性作业车间调度问题时效果显著。通过求解结果对比表明人工蜂群算法的高效性和优越性。     

Metaheuristic methods in hybrid flow shop scheduling problem

Memetic algorithms are hybrid evolutionary algorithms that combine global and local search by using an evolutionary algorithm to perform exploration while the local search method performs exploitation. This paper presents two hybrid heuristic algorithms that combine particle swarm optimization (PSO) with simulated annealing (SA) and tabu search (TS), respectively. The hybrid algorithms were applied on the hybrid flow shop scheduling problem. Experimental results reveal that these memetic techniques can effectively produce improved solutions over conventional methods with faster convergence.     

流水作业批调度问题优化算法研究

为解决流水作业环境作业尺寸有差异的批调度问题,建立了基于混合整数规划方法的最大时间跨度模型,分析问题的计算复杂性,给出设备数、作业数既定情况下的可行解规模.设计一种混合蚁群算法对最大时间跨度进行优化,结合算法的搜索机制和批调度启发式规则,实现了最小化最大时间跨度.利用模拟退火方法改进蚁群算法路径选择,避免算法陷入局部最优和过早收敛.实验设计随机算例,对各类不同规模的算例进行仿真实验,实验结果表明混合蚁群算法在最优解、平均运行时间和最大时间跨度等方面优于其他同类算法.     

Flexible job shop scheduling using hybrid differential evolution algorithms

This paper proposes hybrid differential evolution (HDE) algorithms for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize the makespan. Firstly, a novel conversion mechanism is developed to make the differential evolution (DE) algorithm that works on the continuous domain adaptive to explore the problem space of the discrete FJSP. Secondly, a local search algorithm based on the critical path is embedded in the DE framework to balance the exploration and exploitation by enhancing the local searching ability. In addition, in the local search phase, the speed-up method to find an acceptable schedule within the neighborhood structure is presented to improve the efficiency of whole algorithms. Extensive computational results and comparisons show that the proposed algorithms are very competitive with the state of the art, some new best known solutions for well known benchmark instances have even been found.     

用带蚁群搜索的多种群遗传算法求解作业车间调度问题

结合遗传算法和蚁群算法的优点，提出一种带蚁群搜索的多种群遗传算法．多个种群各自遗传进化，用蚁群搜索得到的解替代各种群中的较劣个体，增加种群的多样性，提高种群的质量；根据各种群最优个体设定初始信息素，大大缩短信息素的累积过程，加快蚁群搜索的速度．利用算法对典型作业车间调度问题进行求解,仿真计算结果表明,该算法是有效的.     

带不相关并行机和有限缓冲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,所提出的混合启发式算法在解的质量方面表现更佳.