求解多目标流水车间调度Pareto最优解的遗传强化算法

针对多目标流水车间调度Pareto最优问题, 本文建立了以最大完工时间和最大拖延时间为优化目标的多目标流水车间调度问题模型, 并设计了一种基于Q-learning的遗传强化学习算法求解该问题的Pareto最优解. 该算法引入状态变量和动作变量, 通过Q-learning算法获得初始种群, 以提高初始解质量. 在算法进化过程中, 利用Q表指导变异操作, 扩大局部搜索范围. 采用Pareto快速非支配排序以及拥挤度计算提高解的质量以及多样性, 逐步获得Pareto最优解. 通过与遗传算法、NSGA-II算法和Q-learning算法进行对比实验, 验证了改进后的遗传强化算法在求解多目标流水车间调度问题Pareto最优解的有效性.     

改进人工蜂群算法求解分布式柔性作业车间调度问题

针对分布式柔性作业车间调度问题的特点,提出一种改进人工蜂群算法.首先,建立以最小化最大完工时间为优化目标的分布式柔性作业车间调度优化模型;然后,改进基本人工蜂群算法以使其适用于求解分布式柔性作业车间调度问题,具体的改进包括设计一种包含三维向量的编码方案,结合问题特点针对性地设计多种策略用于种群初始化,在雇佣蜂改良搜索操作中设计多种有效的进化操作算子,并在跟随蜂搜索操作中引入基于关键路径的局部搜索算子以提升算法的局部搜索能力;最后,利用扩展柔性作业车间通用测试集得到的测试数据设计实验验证算法性能,使用正交试验法优化算法参数设置.仿真实验结果表明,改进后的人工蜂群算法能有效求解分布式柔性作业车间调度问题.     

求解流水车间批量流集成调度的离散入侵杂草优化算法

提出一种离散入侵杂草优化算法,用来解决最大完工时间目标的流水车间批量流集成调度问题.该调度问题包含两个紧密耦合的子问题:批次分割问题和考虑启动时间的批次调度问题.设计了两段字符串编码,用来表示两个子问题.与基本入侵杂草优化算法不同,所提算法基于适应度和年龄确定杂草种子数量,基于正切函数和连续邻域操作产生种子.8种邻域算子的混合应用与局部搜索增强了算法的求解能力.仿真实验表明了所提算法的有效性.     

基于位置与连接概率的EDA算法求解PFSP问题

针对置换流水车间调度问题(PFSP)的特点,提出一种基于工件加工位置与连接概率相结合的混合分布估计算法。该算法将工件位置概率与工件的连接概率结合在一起,作为新一代种群的生成概率从而使得进化趋势更加合理化。为了提高局部搜索能力,算法引入了启发式方法提高初始解质量,优化了邻域搜索策略。同时引入了变异操作及限定操作来提高算法全局搜索能力。实验结果表明,该算法在求解置换流水车间调度问题时具有良好的性能。     

基于和声搜索的阻塞流水车间调度问题的算法优化

针对以最大完工时间为目标的阻塞流水车间调度问题,提出了一种通过混合和声搜索改进遗 传算法的优化求解算法.构建了阻塞流水车间调度原理图并描述了运算方法;详细论述了混合算法的实施流程和关键问题,并使用NEH方法和局部搜索对混合算法进行了改进.仿真结果表明,改进后的混合算法能显著提高优化阻塞流水车间调度问题的解.     

基于机床超低待机状态的流水车间能耗调度

为降低流水车间能源消耗,引入一种数控机床的超低待机状态,相比于将数控机床待机状态切换为停机状态的节能研究,可在不停机情况下降低数控机床加工间隔状态的功率,避免数控机床频繁启停.针对流水车间加工状态、待机状态及超低待机状态三元调度问题,提出基于工序平移的混合遗传算法,分别定义了不同的工序邻域移动操作,实现数控机床待机状态向超低待机状态和停机状态的转化,形成主动节能调度策略,提升遗传算法求解考虑超低待机状态的流水车间调度问题的优化能力.实验研究表明,启用超低待机状态能够降低流水车间10%以上的能耗,且基于工序平移的混合遗传算法求解考虑超低待机状态的流水车间调度问题性能优于遗传算法.     

一种多目标置换流水车间调度问题的优化算法

针对最大完工时间最小和总流经时间最小的多目标置换流水车间调度问题(permutation flow shopscheduling problem, PFSP), 提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化(hybrid particleswarm optimization algorithm, HPSO)算法, 并使算法在集中搜索和分散搜索之间达到合理的平衡. 在该混合算法中,采用NEH 启发式算法进行种群初始化, 以提高初始解质量;运用随机键表示法设计基于升序排列规则(ranked-order-value, ROV), 将连续PSO 算法应用于置换流水车间调度问题;引入外部档案集存贮Pareto 解, 并采用强支配关系和聚集距离相结合的混合策略保证解集的分布性;采用Sigma 法和基于聚集距离的轮盘赌法进行全局最优解的选择;提出变邻域搜索算法, 对外部集中的Pareto 解作进一步地局部搜索. 最后, 运用提出的混合算法求解Taillard 基准测试集, 并将测试结果与SPEA2 算法进行比较, 验证该调度算法的有效性.     

改进蒲公英优化算法的有限缓冲区流水车间调度

针对考虑缓冲区容量限制和机器加工档位的流水车间调度问题(FSSP_LBMPG), 建立了有限缓冲区绿色流水车间数学规划模型, 模型以最小化最大完工时间和最小化加工能量消耗为目标函数, 将缓冲区容量纳入约束, 通过合理选择机器的加工档位达到协调加工速度和加工能耗的效果. 针对问题模型特点, 提出了一种改进蒲公英优化算法(IDOA), 算法首先根据调度问题的特点设计了双层实数编码机制表示问题的解, 通过引入一种初始化机制, 提高初始解质量和求解效率. 算法迭代过程中, 设计了实数交叉策略和变邻域搜索策略, 弥补了原始蒲公英算法局部搜索能力较差的缺点, 提高了改进算法的开发能力. 最后通过设计案例上的对比实验, 表明所提改进措施能有效增强算法性能, 也验证了算法的有效性和鲁棒性.     

求解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算法能够以较快的收敛速度获得柔性流水车间调度问题的一个较好的优化解。     

基于改进蛙跳算法的分布式两阶段混合流水车间调度

针对考虑顺序相关准备时间的分布式两阶段混合流水车间调度问题,提出一种改进的蛙跳算法以同时最小化拖后工件数和最大完成时间.该算法通过启发式方法和随机方法对种群进行初始化,采取基于种群和记忆的种群划分方法,同时给出模因组质量评价方法,并根据模因组质量将所有模因组划分为最优模因组、最差模因组和其他模因组,每种类型的模因组分别采取不同的搜索策略,并分配不同的搜索次数,其中最优模因组不参与种群划分.选用一种多目标经典算法和两种近5年提出的算法作为对比算法,并与改进蛙跳算法的变体进行比较以验证模因组搜索新策略的有效性.通过对大量实例的计算实验结果表明,模因组搜索新策略有效,改进蛙跳算法能有效求解分布式两阶段混合流水车间调度问题.     

基于Q学习算法的作业车间动态调度

近年来,在基于Q学习算法的作业车间动态调度系统中,状态-行动和奖励值靠人为主观设定,导致学习效果不理想,与已知最优解相比,结果偏差较大.为此,基于作业车间调度问题的特质,对Q学习算法的要素进行重新设计,并用标准算例库进行仿真测试.将结果先与已知最优解和混合灰狼优化算法、离散布谷鸟算法和量子鲸鱼群算法在近似程度、最小值方面进行比较分析.实验结果表明,与国内求解作业车间调度问题的Q学习算法相比,该方法在最优解的近似程度上显著提升,与群智能算法相比,在大多数算例中,寻优能力方面有显著提升.     

求解批量流水线调度问题的和声算法

针对以最大完工时间和总流经时间为目标的批量流水线调度问题,提出了改进的和声调度算法。该算法采用基于最大位置值(LPV)规则的编码方式,使具有连续性质的和声算法应用于求解调度问题;提出新的初始化方法,应用了多种群进化的思想更新和声库,并结合和声算法和模拟退火算法各自的特点,给出了两种混合调度算法。仿真实验表明所提算法的可行性和有效性。     

批量无等待调度问题的微粒群蛙跳混合优化算法*

将离散微粒群与蛙跳算法相结合解决以最大完工时间为指标的批量无等待流水线调度问题.结合微粒群算法较强的全局收敛能力和蛙跳算法较强的深度搜索能力,设计了三种混合算法,平衡了算法的全局开发能力和局部探索能力.对随机生成不同规模的实例进行了广泛的实验,仿真实验结果的比较表明了所得混合算法的有效性和高效性.     

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

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

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

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     

确定型流水车间调度的遗传算法研究

为了验证遗传算法在解决确定型流水车间调度问题比其他启发式算法优越,分析了确定型流水车间调度的特点,并运用一种新的遗传算法求解该问题。为了提高效率,避免陷入局部最优,提出了一种合理的种群初始化方法,并成功地运用于求解确定型流水车间调度问题。实验结果证明了改进的遗传算法的实用性和可靠性,并具有较好的应用价值。     

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

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