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

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

融入概率学习的混合差分进化算法求解绿色分布式可重入作业车间调度

本文针对绿色分布式可重入作业车间调度问题(GDRJSSP), 提出一种融入概率学习的混合差分进化算法 (HDE PL), 以实现最大完工时间和总能耗最小. 根据GDRJSSP的问题特点, 设计编码和解码规则, 并采用差分进化 算法执行全局搜索来发现优质解区域. 为能更明确地引导全局搜索方向, 设计基于贝叶斯网络结构的多维概率模型 合理学习和积累优质解(即当前种群中的较优解)的模式信息. 结合问题解的结构特征, 提出基于关键路径的4种邻 域结构来构造局部搜索, 并设计基于非关键路径的节能策略来提升算法获取低能耗非劣解的能力. 仿真实验和算 法对比验证了HDE PL可有效求解GDRJSSP.     

柔性车间调度的解空间距离聚类和变邻域搜索粒子群算法

根据柔性车间调度问题提出基于解空间距离聚类和变邻域搜索的粒子群算法.在粒子群算法基础上采用贪婪策略引入变邻域搜索方式,即调整关键路径上最大关键工序的机器位置,调整关键路径上工序相对位置变化,加强局部搜索能力;根据机器加工工序的空间距离,采用K-means聚类得到机器加工工序“优良个体”,加大局部搜索性能.同时对于粒子群算法速度更新采用局部停滞策略,保留局部片段相对位置不变特性.通过实验仿真,优化算法取得了较好的效果,与一般的粒子群算法相比较收敛速度迅速且性能良好.     

求解区间数分布式流水线调度的混合离散果蝇优化算法

分布式调度是制造系统领域的前沿研究,而不确定调度问题的研究更具现实意义.针对不确定分布式置换流水线调度问题,采用区间数表示工序加工时间,以最小化区间最大完工时间为目标,利用问题特性在果蝇优化框架内提出一种混合离散果蝇优化算法.首先,通过改进启发式方法和随机方法混合初始化种群;然后,基于概率协同多搜索操作执行嗅觉搜索.为了平衡算法的全局探索与局部开发能力,设计基于学习机制的双种群协同搜索环节.为了进一步提升种群性能,针对优良解设计基于切换机制的双模式局部搜索.基于大量算例的仿真结果与统计对比,表明所提出算法能更有效求解区间数分布式流水线调度问题.     

改进松鼠搜索算法求解分布式节能柔性调度

为了优化同时考虑最大完工时间和机器能耗的双目标分布式柔性作业车间调度问题,提出了一种改进的多目标松鼠搜索算法。引入了基于升序排列规则的转换机制,实现了松鼠位置向量与调度解之间的转换,并针对机器空闲时间设计了从半主动到主动的解码策略。针对不同优化目标设计了三种种群初始化策略。同时提出了动态捕食者策略来更好地协调算法的全局探索和局部开发能力。设计了四种领域搜索策略用于增加种群多样。20个实例上的实验结果验证了改进后的算法求得解的质量和多样性更好,从而证明了其可有效求解分布式节能柔性调度问题。     

求解IPPS顺序柔性调度问题的模型与集成型调度算法研究

针对工艺规划与调度集成(integrated process planning and scheduling, IPPS)问题中的顺序柔性调度问题,提出了基于简单顺序关系的顺序柔性描述模型及调度模型,并改进遗传算法设计了集成型的顺序柔性调度算法。染色体编码同时采用简单顺序关系编码和基于工序的编码,并为两种编码分别设计了多种交叉和变异操作。为避免遗传算子产生违背工序顺序优先关系的不可行解,提出了顺序约束修正策略;针对遗传算法易过早收敛的缺陷,设计了自适应调节变量以强化种群多样性,并引入变邻域搜索算法改变解的搜索邻域,进一步搜索最优调度方案。三种不同规模的实验仿真验证了问题描述模型及调度算法的有效性。     

柔性作业车间调度问题的多目标优化算法

柔性作业车间调度问题具有解集多样化与解空间复杂的特点,传统多目标优化算法求解时容易陷入局部最优且丢失解的多样性。在建立以最大完工时间、最大能耗、机器总负荷为优化目标的柔性作业车间调度模型的情况下,提出一种改进的非支配排序遗传算法（Improved Non-dominated Sorting Genetic Algorithm II, INSGA-II）求解该模型。INSGA-II算法先将随机式初始化与启发式初始化方法混合,提高种群多样性;然后对工序部分与机器部分采用针对性的交叉、变异策略,提高算法全局搜索能力;最后设计自适应的交叉、变异算子以兼顾算法的全局收敛与局部寻优能力。在mk01～mk07标准数据集上的实验结果显示INSGA-II算法有着更优的算法收敛性与解集多样性。     

改进多目标进化算法求解柔性作业车间调度问题

针对加工时间为模糊数的柔性作业车间调度问题,考虑最小化模糊最大完工时间、模糊机器总负荷、模糊关键机器负荷为优化目标,提出一种有效求解该类优化问题的多目标进化算法。算法采用一种混合不同机器分配和工序排序策略的方法产生初始种群,并采用插入空隙法对染色体进行解码。定义一种新的基于可能度的个体支配关系和一种基于决策空间的拥挤算子,并将所提支配关系和拥挤算子运用于快速非支配排序。接着,提出一种基于移动模糊关键工序的局部搜索策略对种群中的优势个体进行局部搜索。通过试验研究关键参数对算法性能的影响并将所提算法与3种不同的优化算法作对比。结果表明,所提算法能够比其它算法更有效解决多目标模糊柔性作业车间调度优化问题。     

自适应Jaya算法求解多目标柔性车间绿色调度问题

针对多目标柔性作业车间绿色调度问题(MO-FJGSP),建立优化目标为最大完工时间、机器总负荷和能耗最小的多目标数学模型,并设计一种基于Pareto最优解的自适应多目标Jaya算法(SAMO-Jaya)对该问题进行优化求解.算法采用两级实数编码方式实现工序排序与机器分配的编码表示,并设计一种转换机制实现将Jaya连续解空间映射至FJSP离散解空间;然后设计一种混沌序列与均匀分布相结合的混合策略以提高初始种群的质量与全局分散性;此外,在Jaya算法中嵌入自适应调整种群规模的方法以提高算法求解速度.通过10个单目标与3个多目标基准算例测试,并与7个已有算法进行对比分析,结果表明SAMO-Jaya算法能够对MO-FJGSP进行有效求解.     

求解FFS问题的混合搜索机制粒子群算法

针对柔性流水车间调度(flexible flow shop scheduling,FFS)问题,提出了一种混合搜索机制粒子群算法(multi-search mechanism particle swarm optimization algorithm,MMPSO),以期获得柔性流水车间调度问题的优化解。在分析柔性流水车间调度问题特点的基础上,设计了针对该问题的粒子信息编码方案,提出了瓶颈机器消除算法以提升初始种群的质量;同时在个体极值搜索中采用NEH-Greedy搜索算法,在全体极值搜索中采用SADA(simulated snnealing disturb algorithm)搜索算法以扩大搜索范围,提高可行解质量,加快收敛速度,在算法迭代搜索过程中对全体极值进行RPA(random perturbation algorithm)操作以避免算法陷入局部最优。实验结果表明,MMPSO算法能够以较快的收敛速度获得柔性流水车间调度问题的一个较好的优化解。     

学习驱动的分布式异构混合流水车间批量流能效调度优化

本文研究了分布式异构混合流水车间批量流能效调度问题, 其中每个工厂的加工效率不同, 工件可以分割成若干子批进入加工系统. 以最大完成时间和总能耗为优化目标, 建立了混合整数规划模型. 本文提出了一种学习驱动的多目标进化算法, 包括学习驱动的全局搜索和局部搜索. 引入Q学习作为学习引擎, 以种群和非支配解集的评价作为环境反馈信号, 通过不断的学习来动态指导搜索操作的选择; 基于问题特征, 设计了算法的状态集、动作集和奖励机制. Q学习的引入能够及时感知当前搜索的状态, 减少搜索操作的盲目性, 提高搜索的效率. 通过对仿真数据集的测试, 表明所提出算法能够有效地求解分布式异构混合流水车间批量流能效调度问题.     

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

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

区间数可重入混合流水车间调度与预维护协同优化

针对加工时间不确定的可重入混合流水车间调度与预维护协同优化问题,构建以区间最大完工时间、区间总碳排放和区间总预维护费用为优化目标的集成调度模型.针对问题特性,通过设计改进的可能度计算方法,定义区间意义下解的Pareto占优关系.提出一种改进的离散鲸鱼群算法,通过同步调度与维护策略,实现制造与维护的联合优化;设计个体间距离计算策略,寻找“最近较优个体”;设计个体位置移动策略以及多邻域搜索策略,有效地平衡全局搜索和局部搜索,提高收敛精度.通过大量的仿真实验和结果对比分析,表明了所提出的算法对于求解区间数可重入混合流水车间调度和预维护协同优化问题的有效性和可行性.     

An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers

In this paper, an effective hybrid discrete differential evolution (HDDE) algorithm is proposed to minimize the maximum completion time (makespan) for a flow shop scheduling problem with intermediate buffers located between two consecutive machines. Different from traditional differential evolution algorithms, the proposed HDDE algorithm adopted job permutation to represent individuals and applies job-permutation-based mutation and crossover operations to generate new candidate solutions. Moreover, a one-to-one selection scheme with probabilistic jumping is used to determine whether the candidates will become members of the target population in next generation. In addition, an efficient local search algorithm based on both insert and swap neighborhood structures is presented and embedded in the HDDE algorithm to enhance the algorithm’s local searching ability. Computational simulations and comparisons based on the well-known benchmark instances are provided. It shows that the proposed HDDE algorithm is not only capable to generate better results than the existing hybrid genetic algorithm and hybrid particle swarm optimization algorithm, but outperforms two recently proposed discrete differential evolution (DDE) algorithms as well. Especially, the HDDE algorithm is able to achieve excellent results for large-scale problems with up to 500 jobs and 20 machines.     

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.     

求解无等待流水调度的基于禁忌搜索的混合算法

本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点,首先利用调度规则构造较好的初始解,既可以加快禁忌搜索算法的收敛速度,也可以降低整个算法的运算量,使算法有更好的工程实用性;然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上,该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明,该算法是有效的。     

Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm

Most flexible job shop scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines may be unavailable due to maintenances, pre-schedules and so on. In this paper, we study the flexible job shop scheduling problem with availability constraints. The availability constraints are non-fixed in that the completion time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure. We then propose a hybrid genetic algorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints (fJSP-nfa). The genetic algorithm uses an innovative representation method and applies genetic operations in phenotype space in order to enhance the inheritability. We also define two kinds of neighbourhood for the problem based on the concept of critical path. A local search procedure is then integrated under the framework of the genetic algorithm. Representative flexible job shop scheduling benchmark problems and fJSP-nfa problems are solved in order to test the effectiveness and efficiency of the suggested methodology. Received: June 2005 /Accepted: December 2005     

双资源生产车间调度问题的研究

将遗传算法(GA)和模拟退火算法(SA)相结合研究了双资源生产车间的调度优化问题,该混合算法将机床设备和工人合理地分配给加工任务,使评价性能指标获得最优。通过与国内外学者的算法进行比较,本算法获得的生产周期最短,机床利用率和工人利用率都较高,并且在某些情况下,平均流动时间也较短。因此可以证明本算法具有一定的优越性。     

Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes

In this paper, we investigate a specialized two-stage hybrid flow shop scheduling problem with parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes simultaneously. A novel concept of three-dimensional wasted volume based on the job normal processing time, job size, and job deteriorating rate is first proposed. Some structural properties, as well as a heuristic algorithm, are developed to solve the single parallel batching machine scheduling problem. Since the two-stage hybrid flow shop scheduling problem is NP-hard, a hybrid EDA-DE algorithm combining estimation of distribution algorithm (EDA) and differential evolution (DE) algorithm is proposed to tackle the studied problem. In addition, the Taguchi method of design of experiments (DOE) is implemented to tune the parameters of the EDA-DE. Finally, a series of computational experiments are carried out to compare the performance of the proposed hybrid EDA-DE algorithm and some recent existing algorithms from the literature, and the comparative results validate the effectiveness and efficiency of the proposed algorithm.     

Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer

The no-wait job shop scheduling problem is a well-known NP-hard problem and it is typically decomposed into timetabling subproblem and sequencing subproblem. By adopting favorable features of the group search technique, a hybrid discrete group search optimizer is proposed for finding high quality schedules in the no-wait job shops with the total flow time criterion. In order to find more promising sequences, the producer operator is designed as a destruction and construction (DC) procedure and an insertion-based local search, the scrounger operator is implemented by differential evolution scheme, and the ranger operator is designed by hybridizing best insert moves. An efficient initialization scheme based on Nawaz–Enscore–Ham (NEH) heuristic is designed to construct the initial population with both quality and diversity. A speed-up method is developed to accelerate the evaluation of the insertion neighborhood. Computational results based on well-known benchmark instances show that the proposed algorithm clearly outperforms a hybrid differential evolution algorithm and an iterated greedy algorithm. In addition, the proposed algorithm is comparable to a local search method based on optimal job insertion, especially for large-size instances.