粒子群算法解决置换流水车间调度问题方法综述

置换流水车间调度问题是典型的NP问题,近年来随着粒子群算法的出现和发展,用来解决车间生产调度问题的粒子群思想和方法也层出不穷。为了促进粒子群算法的进一步发展,更好地解决流水车间调度问题以及为设计更好的算法提供参考,对粒子群算法解决生产调度问题的各个步骤所采用的方法进行总结,分析了各种方法的适用范围,为设计更好的算法奠定了良好的基础;最后探讨了粒子群算法求解置换流水车间调度问题有待进一步研究的若干方向和内容。     

面向IC生产模式的Job Shop调度问题的研究

针对即时定制生产模式的车间调度的特点,提出基于粒子群算法(PSO)的车间调度问题的解决方案.利用粒子群算法本身的优越性解决复杂的车间作业排序问题,克服了传统调度算法存在寻优效率低或全局寻优能力差的弱点.对粒子群的编码及寻优操作进行研究,确定了更适合车间调度问题的编码和操作方式,并将算法进行编程,应用到系统的车间调度部分.仿真结果表明,通过设置适当的参数,可以快速地得到理想的排序结果,能够适用于IC生产模式的车间调度问题.     

基于Petri网和混合算法的作业车间优化

采用赋时变迁Petri网,建立了一种作业车间调度模型.通过为机器分配工序来消解因机器库所共享而引起的冲突,得到了表示调度方案的标志图,给出了一种生成可行调度标志图的方法.同时,提出了一种变迁激发序列编码的离散版粒子群算法,并将模拟退火算法嵌入到该粒子群算法中,以提高算法的优化性能.仿真结果验证了混合算法的可行性和有效性.     

置换流水车间调度的文化量子粒子群算法

针对量子粒子群算法在求解置换流水车间调度问题时容易早熟,提出用文化量子粒子群算法求解置换流水车间调度问题.该算法的主群体空间采用量子粒子群算法,知识空间采用遗传算法.通过影响操作和接受操作,知识空间定期将自己的精英个体贡献给主群体空间,主群体空间也定期将自己的精英个体贡献给知识空间.最后将该算法应用到具体问题的求解,用MATLAB编程仿真测试,仿真结果表明,该算法收敛速度快,且具有较高的求解质量,而且其搜索性能优于一般的量子粒子群算法.     

动态环境下的柔性作业车间调度问题研究

针对动态环境下的柔性作业车间调度问题,提出了一种基于改进离散粒子算法的动态调度方法。动态调度方法采用在动态车间调度中应用最为广泛的滚动窗口与改进离散粒子算法相结合的再调度策略,最后通过对两类突发动态事件的仿真测试,验证了本文所提方法能够解决各类突发动态事件,及时有效地对初始方案进行调整,并与原方案有效衔接。     

基于知识进化粒子群算法的模糊交货期流水车间调度问题

针对模糊交货期的流水车间调度问题的特点,提出采用知识进化算法和粒子群优化的混合算法来求解问题。该算法首先在多个群体空间内采用粒子群优化寻找局部最优解,然后利用知识进化算法的猜测操作和反驳操作建立以群体空间知识为基础的一个知识空间,最后通过知识空间的协同进化更新其中的社会知识,从而形成问题的最优解。通过采用所提算法对带模糊交货期的流水车间调度问题的实例进行测试,并比对遗传算法和粒子群优化算法,表明了混合算法的可行性和有效性。     

混沌压缩非线性粒子群算法求解车间调度问题

针对大规模车间调度问题,提出了一种混沌压缩非线性粒子群算法。首先运用多种群策略增加粒子多样性,结合混沌策略和非线性策略改进惯性权重,以平衡全局和局部搜索能力,加快算法后期收敛速度;再引入压缩因子改进算法速度更新公式,加大算法前期搜索范围,以防止算法陷入局部最优;最后用6种车间作业经典算例分别对粒子群算法、遗传算法、灰狼算法和混沌压缩非线性粒子群算法进行检验。实验结果表明,该方法可以显著提升粒子群算法的收敛精度和速度,对于实际大规模车间调度问题适应性较好,能有效提高车间的生产效率。     

采用量子粒子群算法的一类模糊作业车间调度问题的研究

针对一类具有模糊加t时间和模糊交货期的作业车间调度问题,提出一种收敛速度快、全局性能好、不易陷入局部最优的智能迭代算法--量子粒子群算法,对其进行求解.通过仿真实例对此算法进行验证,结果表明,在求解带模糊加丁时间和模糊交货期的作业车间调度问题时,量子粒子群算法有很好的效果.     

列车调度问题模型与基于混合粒子群优化的求解算法

针对复线列车调度问题,建立了描述问题解空间的阻塞限制混合流水车间模型,并提出一种混合粒子群优化算法进行求解。该算法以最小化最长完工时间为目标,设计了释放-回推算法来安排列车运行顺序并计算最小化最长完工时间,利用改进的粒子群优化算法解决轨道分配问题并进行全局优化。此外,通过基于迭代邻域的搜索算法来提高种群的局部搜索能力。实验结果表明,所提出的方法能够有效地求解复线列车调度问题。     

协同PSO算法在Job-Shop调度中的应用

提出一种解决车间调度作业的有效改进型粒子群算法,该算法可以有效地避开标准粒子群算法局部搜索能力较差、搜索精度不够高、容易陷入局部极小解等缺点,并通过实例验证了该算法的有效性与可行性。     

Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems

This paper addresses multi-objective job shop scheduling problems with fuzzy processing time and due-date in such a way to provide the decision-maker with a group of Pareto optimal solutions. A new priority rule-based representation method is proposed and the problems are converted into continuous optimization ones to handle the problems by using particle swarm optimization. The conversion is implemented by constructing the corresponding relationship between real vector and the chromosome obtained with the new representation method. Pareto archive particle swarm optimization is proposed, in which the global best position selection is combined with the crowding measure-based archive maintenance, and the inclusion of mutation into the proposed algorithm is considered. The proposed algorithm is applied to eight benchmark problems for the following objectives: the minimum agreement index, the maximum fuzzy completion time and the mean fuzzy completion time. Computational results demonstrate that the proposal algorithm has a promising advantage in fuzzy job shop scheduling.     

多目标批量生产柔性作业车间优化调度

研究批量生产中以生产周期、最大提前/最大拖后时间、生产成本以及设备利用率指标(机床总负荷和机床最大负荷)为调度目标的柔性作业车间优化调度问题。提出批量生产优化调度策略,建立多目标优化调度模型,结合多种群粒子群搜索与遗传算法的优点提出具有倾向性粒子群搜索的多种群混合算法,以提高搜索效率和搜索质量。仿真结果表明,该模型及算法较目前国内外现有方法更为有效和合理。最后,从现实生产实际出发给出多目标批量生产柔性调度算例,结果可行,可对生产实践起到一定的指导作用。     

Reentrant two-stage multiprocessor flow shop scheduling with due windows

Reentrant flow shop scheduling allows a job to revisit a particular machine several times. The topic has received considerable interest in recent years; with related studies demonstrating that particle swarm algorithm (PSO) is an effective and efficient means of solving scheduling problems. By selecting a wafer testing process with the due window problem as a case study, this study develops a farness particle swarm optimization algorithm (FPSO) to solve reentrant two-stage multiprocessor flow shop scheduling problems in order to minimize earliness and tardiness. Computational results indicate that either small- or large-scale problems are involved in which FPSO outperforms PSO and ant colony optimization with respect to effectiveness and robustness. Importantly, this study demonstrates that FPSO can solve such a complex scheduling problem efficiently.     

基于改进粒子群算法的车间作业排序的优化设计

兼顾车间作业排序中的制造周期和机器利用率,建立了以最小化最大完工时间为主目标、以最大化机器利用率为从目标的优化模型。设计了引入自适应技术的惯性权重,使基本粒子群算法的学习因子可动态变化地改进粒子群算法,并用该改进后的算法对车间作业排序进行了优化设计。实例研究表明:改进后的粒子群算法在收敛速度和收敛可靠性上均优于未改进的粒子群算法,在求解车间作业排序问题的应用中具有更高的求解质量。     

基于改进粒子群算法的车间作业排序的优化设计

兼顾车间作业排序中的制造周期和机器利用率,建立了以最小化最大完工时间为主目标、以最大化机器利用率为从目标的优化模型。设计了引入自适应技术的惯性权重,使基本粒子群算法的学习因子可动态变化地改进粒子群算法,并用该改进后的算法对车间作业排序进行了优化设计。实例研究表明：改进后的粒子群算法在收敛速度和收敛可靠性上均优于未改进的粒子群算法,在求解车间作业排序问题的应用中具有更高的求解质量。     

基于混合粒子群算法具有交货期瓶颈的作业车间调度问题

为了解决一类具有交货期瓶颈的作业车间调度问题,给出了基于订单优势的交货期满意度和交货期瓶颈资源确定方法,以工件拖期加权和最小为优化目标,建立了基于交货期满意度和瓶颈资源约束的作业车间调度模型;为了求解该调度模型,设计了一种基于模拟退火的混合粒子群算法,该算法采用随机工序表达方式进行编码,并在模拟退火算法中引入变温度参数来提高算法效率。通过随机仿真,分别采用PSO-SA、SA和PSO对所建立的调度模型进行求解,结果显示PSO-SA算法的广泛性好、求解效率高且算法的稳定性好,验证了模型和算法的有效性。     

解决无等待流水线调度问题的新算法

提出了解决无等待流水线调度问题的3种新算法,即离散粒子群优化算法、离散差异进化算法和阈值接收算法。离散粒子群优化算法和离散差异进化算法采用了基于工件序列的编码方式和新的个体生成方法,从而使具有连续性质的粒子群优化算法和差异进化算法能直接用于求解调度问题。仿真试验表明了上述算法的有效性。     

Hybrid meta-heuristic algorithm for job shop scheduling with due date time window and release time

This study intends to solve the job shop scheduling problem with both due data time window and release time. The objective is to minimize the sum of earliness time and tardiness time in order to reduce the storage cost and enhance the customer satisfaction. A novel hybrid meta-heuristic which combines ant colony optimization (ACO) and particle swarm optimization (PSO), called ant colony–particle swarm optimization (ACPSO), is proposed to solve this problem. Computational results indicate that ACPSO performs better than ACO and PSO.     

工艺计划与车间作业计划集成系统的研究

分析了现有工艺计划与车间作业计划的系统集成模型,建立了企业生产工艺计划与作业计划的层次结构,提出了面向车间作业计划的动态、分布式工艺计划与车间作业计划集成模型。将工艺计划与基于周期和事件驱动的动态作业计划相结合,把改进的离散化粒子群算法引入车间优化作业计划运算,使集成模型中生产作业计划与控制功能得以实现。实例证明了集成系统的可行性和有效性。