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

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

基于自适应参数与混沌搜索的PSO算法求解柔性作业车间调度问题

针对传统粒子群优化(PSO)算法在求解柔性作业车间调度问题中的不足,提出了基于自适应参数与混沌搜索的粒子群优化算法。对粒子群算法中的惯性系数等参数采用基于迭代搜索而自适应调整的方式,使粒子在初期以较大惯性进行大范围搜索,后期逐渐减小惯性而转入精细搜索。这种方法改变了传统粒子群算法在求解过程中的盲目随机与求解精度不高的问题;同时,通过在局部搜索过程中引入混沌技术,扩大对最优解的寻找范围,以此避免算法陷入局部最优,有效提高算法的全局寻优能力。实验结果表明,基于自适应参数与混沌搜索的粒子群优化算法在求解柔性作业车间调度问题(FJSP)时能够获得更优粒子适应度平均值及更好的优化目标。所提算法对求解柔性作业车间调度问题可行,有效。     

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

改进的离散型萤火虫优化算法求解柔性作业车间调度问题

针对传统的群智能优化算法在求解柔性作业车间调度问题(FJSP)时,存在寻优能力不足且易陷入局部最优等缺点,本文以最小化最大完工时间为目标,将萤火虫算法(FA)用于求解柔性作业车间调度问题,提出一种改进的离散型萤火虫算法(DFA)。首先,通过两段式编码建立FA连续优化问题与FJSP离散优化问题之间的联系;其次,设计一种群初始化方法,以确保初始解的质量以及多样性;然后,提出改进离散型萤火虫优化算法并引入局部搜索算法,加强算法的全局搜索能力和局部搜索能力;最后,对标准算例进行仿真,验证DFA算法求解FJSP的有效性。通过与遗传算法和粒子群优化算法进行仿真对比,表明了DFA求解FJSP的优越性。     

粒子群算法求解具有机器灵活性的FFSP

对柔性流水车间调度问题(FFSP)进行了分析阐述,在此基础上对某饲料厂的饲料生产过程建立了具有机器灵活性的柔性流水车间调度模型,该模型中存在多台制粒机,既能加工大颗粒饲料,又能加工小颗粒饲料,但是必须在开始加工之前确定各台机器的用途,增加了柔性流水车间调度的难度。利用新型的粒子群算法以最小化最大完工时间为目标对该模型求解,为了克服粒子群算法易陷入局部极值的缺点,提出基于位置相似度的邻域结构,并对邻域内的较优粒子采用基于最大完工时间排序的学习方式进行局部搜索。实验结果表明,该方法有利于克服粒子群算法的早熟缺陷,有效地解决了饲料生产调度问题,有一定的应用价值。     

新型离散蝙蝠算法求解柔性流水车间调度问题

针对以最小化完工时间为目标的柔性流水车间调度问题,提出了一种新型离散蝙蝠算法。介绍了蝙蝠算法的基本思想,重新定义速度与位置的加法操作来实现粒子的位移,给出了算法的具体实现方案。通过实例仿真和算法比较验证了算法的优化性能,实验结果表明该算法可以有效地求解柔性流水车间调度问题。     

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

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

一种新的混合粒子群算法求解置换流水车间调度问题

针对粒子群算法易早熟的缺点,提出了一种结合迭代贪婪(IG)算法的混合粒子群算法。算法通过连续几代粒子个体极值和全局极值的变化判断粒子的状态,在发现粒子出现停滞或者粒子群出现早熟后,及时利用IG算法的毁坏操作和构造操作对停滞粒子和全局最优粒子进行变异,变异后利用模拟退火思想概率接收新值。全局最优粒子的改变会引导粒子跳出局部极值的约束,增加粒子的多样性,从而克服粒子群的早熟现象。同时,为了使算法能更快找到或逼近最优解,采用了循环迭代策略,在阶段优化结果的基础上,周而复始循环迭代进行求解。将提出的混合粒子群算法应用于置换流水车间调度问题,并在问题求解时与几个具有代表性的算法进行了比较。结果表明,提出的算法能够克服粒子群早熟,在求解质量方面优于其他算法。     

单线列车调度问题的双向阻塞车间调度模型及其粒子群求解算法

针对单线列车调度问题的特点,以线路中列车的总运行时间最小为目标,建立了可以直观描述问题解空间的双向阻塞车间调度模型,并提出了一种有效的离散粒子群优化算法进行求解。该算法基于双向阻塞车间调度模型设计了排列编码形式,从而可确定列车的运行顺序,同时利用随机策略和运行时间最短优先策略选择列车运行轨道;算法在求解过程中,提出了列车冲突的检测和化解方法,并按照“调度-检测冲突-化解冲突”的步骤逐区段调度列车运行;最后,利用离散粒子群优化算法进行全局优化,得到问题的最优解。仿真实例表明,所得模型和算法能够高效地求解单线列车调度问题。     

改进的粒子群算法求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种改进的粒子群算法进行求解。改进算法引入了判断粒子群早熟的方法,并在发现粒子群早熟后采用逆转策略对种群最优粒子进行变异,利用模拟退火思想概率接收新的最优粒子。种群最优粒子的改变会引导粒子群跳出局部极值的约束,从而克服粒子群的早熟状态。通过对置换流水车间调度问题中Car系列和Rec系列部分基准数据的测试,证明了该算法的有效性。     

A novel hybrid algorithm for scheduling steel-making continuous casting production

In this paper, steel-making continuous casting (SCC) scheduling problem (SCCSP) is investigated. This problem is a specific case of hybrid flow shop scheduling problem accompanied by technological constraints of steel-making. Since classic optimization methods fail to obtain an optimal solution for this problem over a suitable time, a novel iterative algorithm is developed. The proposed algorithm, named HANO, is based on a combination of ant colony optimization (ACO) and non-linear optimization methods.     

The economic lot scheduling problem in limited-buffer flexible flow shops: Mathematical models and a discrete fruit fly algorithm

This paper considers the lot scheduling problem in the flexible flow shop with limited intermediate buffers to minimize total cost which includes the inventory holding and setup costs. The single available mathematical model by Akrami et al. (2006) for this problem suffers from not only being non-linear but also high size-complexity. In this paper, two new mixed integer linear programming models are developed for the problem. Moreover, a fruit fly optimization algorithm is developed to effectively solve the large problems. For model’s evaluation, this paper experimentally compares the proposed models with the available model. Moreover, the proposed algorithm is also evaluated by comparing with two well-known algorithms (tabu search and genetic algorithm) in the literature and adaption of three recent algorithms for the flexible flow shop problem. All the results and analyses show the high performance of the proposed mathematical models as well as fruit fly optimization algorithm.     

解决零空闲流水线调度问题的离散粒子群算法

研究了以最大完工时间为目标的零空闲流水线调度问题.提出一种复杂度为O(nm)的最大完工时间算法和一种快速插入邻域搜索算法;提出了解决该问题的离散粒子群调度算法,并结合简化邻域搜索算法给出了提高调度算法性能的措施.仿真实验表明了所得算法的有效性.     

A Decomposition and Coordination Scheduling Method for Flow-shop Problem Based on TOC

There are many flow shop problems of throughput (denoted by FSPT) with constraints of due date in real production planning and scheduling. In this paper, a decomposition and coordination algorithm is proposed based on the analysis of FSPT and under the support of TOC (theory of constraint). A flow shop is at first decomposed into two subsystems named PULL and PUSH by means of bottleneck. Then the subsystem is decomposed into single machine scheduling problems, so the original NP-HARD problem can be transferred into a serial of single machine optimization problems finally. This method reduces the computational complexity, and has been used in a real project successfully.     

基于TSAPO的柔性作业车间计划和调度

为使多目标柔性作业车间计划与调度的制定更适合实际生产的动态变化,提出增加动态反馈的闭环柔性作业车间计划模型及二阶式蚁群粒子群混合优化算法TSAPO。通过增加动态监视功能,及时更新和反馈实际生产数据。利用对优化目标的二阶段分解,设计带有反馈机制的调度算法。实验结果证明,该算法在求解多目标柔性作业车间调度问题中具有较好的优化效果。     

周期性和事件驱动的JobShop滚动调度策略

为了适应加工的连续性及环境的变化，借用了预测控制中的滚动优化思想提出了周期性和事件驱动的滚动调度策略。调度算法将遗传算法和分派规则相结合，以此来处理与操作序列有关的工件安装时 间和工件到期时间约束的复杂调度问题。     

基于约束理论的Flow-shop分解协调算法

There are many flow shop problems of throughput (denoted by FSPT) with constraints of due date in real production planning and scheduling. In this paper, a decomposition and coordination algorithm is proposed based on the analysis of FSPT and under the support of TOC (theory of constraint). A flow shop is at first decomposed into two subsystems named PULL and PUSH by means of bottleneck. Then the subsystem is decomposed into single machine scheduling problems, so the original NP-HARD problem can be transferred into a serial of single machine optimization problems finally. This method reduces the computational complexity, and has been used in a real project successfully.     

An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

无等待流水车间调度问题的优化

文中研究了以生产周期为目标的无等待流水车间调度问题.首先,结合问题特征,提出了一种复杂度为O(n)的快速生产周期算法.其次,研究了两种插入邻域结构:基本插入邻域和多重插入邻域,并提出了快速基本插入邻域算法和最大多重插入移动算法.在此基础上,将离散粒子群算法与上述两种邻域搜索算法相结合,得到了离散粒子群优化调度算法.第三,根据问题生产周期的不规则性,给出了一种通过延长工序加工时间进一步改进调度方案的方法.最后,仿真实验表明了所得算法的可行性和有效性.