两机无等待流水车间调度问题的性质

针对两机无等待流水车间调度问题,提出目标函数最大完工时间最小化的快速算法,并给出算法的复杂度。分析两机无等待流水车间调度问题的排列排序性质,证明了两机无等待流水车间调度问题的可行解只存在于排列排序中,排列排序的最优解一定是两机无等待流水车间调度问题的最优解。最后研究了同时包含普通工件和无等待工件的两机流水车间调度问题的复杂性,为进一步研究两机无等待流水车间调度问题提供了理论依据。     

求解具有混合约束流水车间调度问题的迭代贪婪算法

流水车间调度问题是具有典型工程应用背景的组合优化问题,对该问题的研究具有重要的理论意义和应用价值。基于传统的流水车间调度问题,提出一种有限等待约束、阻塞约束以及无等待约束共存的混合约束流水车间调度问题。以问题的最小化最大完工时间为目标,提出一种利用迭代贪婪算法进行求解的方法,该方法利用改进的NEH算法计算初始解,通过迭代贪婪算法进行优化,并设计多点交叉策略和插入邻域搜索策略提高解的质量。通过经典实例测试,验证了所提算法的有效性。     

应用萤火虫算法求解基于学习效应的PFSP问题

针对置换流水车间调度问题,应用学习效应理论,将工件的加工时间与工件的加工位置建立联系,缩短了工件的最大完工时间,并将不同学习率下的最小化最大完工时间进行比较,给生产制造企业合理安排生产计划提供借鉴。应用MATLAB软件编写萤火虫算法,对建立的模型进行仿真测试,通过与粒子群算法和遗传算法进行结果对比,验证了算法的有效性,在此基础上求解出具有不同学习率的置换流水车间调度问题的最小化最大完工时间。     

量子萤火虫算法及在无等待流水调度上的应用

针对无等待流水车间调度问题,提出了一种新颖的量子萤火虫优化算法用于最小化总完工时间．首先,将量子进化机制嵌入萤火虫算法中,并设计一种快速的局部邻域搜索方法,在每次迭代时只搜索部分邻域,同时采用目标增量计算邻域解变化,这样极大地加快了算法迭代速度,加速了算法收敛．最后,应用Taillard基准测试实例仿真,与目前较优的启发式算法IHA（improved heuristic algorithm）和群智能算法DGSO（discrete glowworm swarm optimization）、 GA-VNS（genetic algorithm-variable neighborhood search）及DHS（discrete harmony search）相比较,产生最好解的平均百分比偏差均下降了40％以上．实验结果验证了所提算法在求解无等待流水调度中的优越性．     

蚁群优化结合变邻域搜索求解NWFS调度问题

针对NP-难的最小化时间表长为目标的无等待流水车间调度问题,将此问题转化为旅行商问题.采用蚁群优化求得初始工件排序.在提出的一种新的邻域结构基础上,迭代进行集中和分散的变邻域搜索以改善解.用Rec系列及he11和he12共计23个Benchmark算例进行计算验证,并与RAJ算法进行了比较.结果表明所提出的方法是有效的.     

改进离散粒子群算法求解柔性流水车间调度问题

针对以最小化完工时间为目标的柔性流水车间调度问题(FFSP),提出了一种改进离散粒子群(DPSO)算法.所提算法重新定义粒子速度和位置的相关算子,并引入编码矩阵和解码矩阵来表示工件、机器以及调度之间的关系.为了提高柔性流水车间调度问题求解的改进离散粒子群算法的初始群体质量,通过分析初始机器选择与调度总完工时间的关系,首次提出一种基于NEH算法的最短用时分解策略算法.仿真实验结果表明,该算法在求解柔性流水车间调度问题上有很好的性能,是一种有效的调度算法.     

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

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

工件可拒绝的有限等待置换流水车间调度算法

有限等待限定了工件在相邻机器间的等待时间上下限,普遍存在于中间产品性质不稳定且存在运输作业的车间环境中.工件可拒绝的有限等待置换流水车间调度是对工件拒绝和工件调度的联合决策,要求确定拒绝工件集合并给出被接受工件的调度方案.针对这一联合决策问题,以最小化总拒绝成本与总拖期成本之和为目标,并为最大完工时间(Makespan)设置上限约束,结合问题特征提出一种协同进化遗传算法.该算法将染色体编码分解为工件拒绝和工件序列两个子集,基于调度规则生成初始种群,引入协同进化策略依次进化子集种群,并提出基于记忆的动态概率参数设计方法以确定遗传算子的执行概率,设计解码规则以保证解的可行性并优化总成本.最后,通过数据实验验证了所提出算法及相关策略的可行性和有效性,并分析了问题参数对算法性能的影响.     

双目标无等待流水线调度的加权混合算法

针对最小化“总完工时间”和“最大完工时间”的双目标无等待流水线作业调度问题提出了一种粒子群加权混合优化算法,通过随机加权的方式将其转换成单目标问题,并应用基于升序排列的ROV（ranked-order-value）编码规则,将粒子群优化算法应用于无等待流水线作业调度问题。为了提高算法的性能,增强算法的搜索能力,提出的混合算法应用了NEH方法构造初始种群,在一个较好的初始值上进行粒子群优化,为防止种群陷入局部最优造成早熟,在粒子群每次迭代之后对全局最优解加入扰动并进行变邻域搜索。仿真实验结果表明该混合调度算法具有良好的性能。     

有准备时间无等待流水车间调度的搜索算法

利用迭代变化邻域搜索算法(IVNS)求解最小化总完工时间的有准备时间无等待流水车间调度问题. 设计局部搜索算法需要考虑3个关键因素：所用邻域、解评估和局部最优的克服. 因此,定义了3个较大规模邻域以扩大搜索范围. 为加速解评估,利用目标增量来避免重新计算每个解的目标函数值,使相邻解比较只需常量时间,NEH插入算法的时间复杂度降低一阶. IVNS通过切换邻域和扰动重启,来克服局部搜索易于陷入局部最优解的缺点. 通过与求解该问题的当前最好算法在5400个标准算上,以相同CPU时间进行的实算比较,实验结果统计分析验证了IVNS的寻优性能明显优于参照算法.     

基于混合差分进化算法的无等待流水车间总流水时间优化*

以调度的总流水时间为优化目标, 提出一种混合差分进化算法。 首先, 建立无等待流水车间调度的问题模型,并用快速方法评估总流水时间指标。 其次,采用LPV规则,实现离散问题的连续编码; 用差分进化算法对总流水时间指标执行优化;引入插入邻域和基于pairwise的局部搜索算法, 分别对差分进化算法产生的新个体和差分进化算法的最优解执行邻域搜索, 达到优化目标全局和局部的最优。 最后,通过计算标准算例, 并与其他算法比较, 验证该混合差分进化算法的有效性。     

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

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

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.     

An improved heuristic for no-wait flow shop to minimize makespan

No-wait flow shop production has been widely applied in manufacturing, where no waiting time is allowed between intermediate operations. However, minimization of makespan for no-wait flow shop production is NP-hard. In this paper, we propose an average idle time (AIT) heuristic to minimize makespan in no-wait flow shop production. First, we take the current idle times and future idle times into consideration, proposing an initial sequence algorithm, and then use the insertion and neighborhood exchanging methods to further improve solutions. Compared with three existing best-known heuristics, our AIT heuristic can achieve the smallest deviations of 0.23% from optimum, based on Taillard’s benchmarks and 600 randomly generated instances, in the same computational complexity.     

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.     

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

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

动态零等待流水线调度问题的滚动策略及优化算法

针对工件动态到达的零等待流水线调度问题,提出一种基于工件的滚动策略.证明了在该策略下全局调度性能随着局部调度的逐步滚动可得到不断改善.将该策略与基于差分进化的混合算法有机结合,能有效处理动态零等待流水线调度问题.最后通过实验验证了所提出策略和算法的有效性.