基于粒子群优化和变邻域搜索的混合调度算法

提出了用于解决作业车间调度问题的离散版粒子群算法.该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题.同时,针对粒子群算法容易陷入局部最优的缺陷,利用粒子群算法和变邻域搜索算法的互补性能,设计了粒子群-变邻域搜索算法、改进的粒子群算法、粒子群-变邻域搜索交替算法和粒子群-变邻域搜索协同算法4种混合调度算法.仿真结果表明,混合算法能够有效地、高质量地解决作业车间调度问题.     

物流自动化仓库拣选作业调度粒子群优化研究

建立自动化仓库堆垛机拣选作业调度模型,采用粒子群算法对拣选作业调度进行优化。提出一种基于货位和粒子位置的二维粒子编码方法,并采用基于粒子位置互换操作的局部搜索方法。计算结果说明,混合粒子群算法能够有效地对自动化仓库拣选作业调度进行优化。     

置换流水车间调度粒子群优化与局部搜索方法研究

采用粒子群优化算法求解置换流水车间调度问题,提出了一种基于工件次序和粒子位置的二维粒子编码方法.为提高粒子群算法的优化性能,在描述了面向置换流水车间调度问题的粒子邻域结构后,提出了三种基于粒子邻域操作的局部搜索方法,分别是基于互换操作、基于插入操作和基于逆序操作的局部搜索方法.计算结果说明,粒子群算法的优化性能好于遗传算法和NEH启发式算法.三种局部搜索算法均能有效地提高粒子群算法的优化性能,采用基于互换操作局部搜索的粒子群算法的优化性能要好于其它两种局部搜索算法.     

并行机调度问题粒子群优化研究

采用粒子群算法优化并行机调度问题,提出了基于机器和粒子位置取整的粒子编码方法和基于工件和粒子位置次序的粒子编码方法,并给出了两种不同粒子编码方法所对应的粒子群算法的步骤.通过对两个并行机算例的计算说明,基于两种不同编码方法的粒子群算法都能有效地对并行机调度问题进行优化,其中,基于工件和粒子位置次序的粒子编码所对应粒子群算法的优化性能要好些.     

基于混沌粒子群算法的单台批加工设备调度

提出了一种基于混沌粒子群算法的双层调度方法。双层调度的外层基于加工时间最小的目标构建组批方法集,然后将其作为内层算法的搜索空间;双层调度的内层以加工时间最小为适应值函数,采用混沌粒子群算法求解批次排序的最优解,得到最优的组批方法及其排序。通过仿真验证了该算法在搜索时间和搜索精度的可行性。     

求解Job shop调度的协同优化算法

针对量子粒子群算法、遗传算法在求解车间调度存在的局部收敛的问题,提出用量子粒子群算法与遗传算法相结合的协同优化方法求解该问题。该算法采用量子粒子群算法与遗传算法的并行搜索结构,通过迁移算子把各个种群联系起来。仿真结果表明,该算法收敛速度快,且具有较高的求解质量。     

求解作业车间调度问题的广义粒子群优化算法

为克服传统粒子群优化算法在解决组合优化问题上的局限性,分析了其优化机理,并在此基础上提出了广义粒子群优化模型。按照此模型提出了一种求解作业车间调度问题的广义粒子群优化算法。在本算法中,利用遗传算法中的交叉操作作为粒子间的信息交换策略,利用遗传算法中的变异操作作为粒子的随机搜索策略,而粒子的局部搜索策略则采用禁忌搜索来实现。为了控制粒子的局部搜索以及向全局最优解的收敛,迭代过程中交叉概率以及禁忌搜索的最大步长都是动态变化的。实验结果表明,本算法可有效地求解作业车间调度问题,验证了广义粒子群优化模型的合理性。     

解决零等待多产品厂调度问题的改进粒子群算法

针对零等待多产品厂调度问题的总流程时间最小化问题,提出一种改进粒子群算法。在该类问题中,产品在每台设备上的操作包括调整、加工和移除三部分,并以零等待方式进行生产。对生产过程的特殊性建立了调度问题的数学模型,在分析了标准粒子群算法所固有的缺陷的基础上提出一种带有创新因子的改进粒子群算法。通过在粒子的位置更新公式中加入创新因子,提高了粒子的随机性,使粒子不再单纯跟踪个体极值和群体极值,避免了粒子快速聚集到群体极值周围,同时扩大了搜索范围,使粒子获得了更好的"探索"能力,增强了种群在进化过程中的多样性,防止算法陷入局部最优,提高了算法的全局搜索能力。通过对不同规模问题的仿真求解,改进算法的优化结果明显优于标准粒子群算法和遗传算法,表明了改进算法的有效性和优越性。最后,仿真讨论了非零调整时间和非零移除时间对调度结果的影响。     

基于粒子群优化和模拟退火的混合调度算法

提出了一种离散粒子群调度算法，采用基于工序的编码方式及相应的位置和速度更新方法，使具有连续本质的粒子群算法直接适用于调度问题。针对粒子群算法容易陷入局部最优的缺陷，将其与模拟退火算法结合，得到了粒子群-模拟退火算法、改进的粒子群算法、粒子群-模拟退火交替算法以及粒子群-模拟退火协同算法等4种混合调度算法。仿真结果表明，混合算法均具有较高的求解质量。     

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

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

交货期惩罚下柔性车间调度多目标Pareto优化研究

针对传统作业车间调度问题的局限性,结合实际生产过程的特点和约束条件,建立路径柔性的作业车间调度仿真模型。采用连续空间蚁群算法,对柔性车间作业进行多变量、多约束下的调度布局优化设计,在考虑各个机器提前/拖期完工的惩罚值,所有机器上的总负荷、成品合格率和最大设备利用率等性能指标更加合理情况下,为每次迭代产生的邻域解集作为Pareto非支配排序,防止算法操作过程中劣解的产生,提高求解效率。并与自适应免疫算法和交换序列混合粒子群法的优化结果进行对比,该算法可有效改善基本蚁群算法的停滞现象和全局寻优能力差的缺点。目前,该方法已在某机械公司进行示范,在提高加工效率、降低生产成本、减少协作费等方面效果显著。     

基于禁忌搜索的平行机多工厂供应链调度

提出一类平行机多工厂供应链调度问题,从整体的角度优化订单分配、生产调度和运输调度。以交货期限内完成所有工件的生产和运输总成本最小化为目标,构建了问题的混合整数规划模型。设计了一种基于向量组编码结构的禁忌搜索算法以求解该问题。使用供应链调度策略和独立决策策略分别对算例进行求解,数据结果验证了供应链调度策略的优越性。禁忌搜索算法结果与CPLEX的求解结果对比表明,禁忌搜索算法有效可行。     

APPLYING PARTICLE SWARM OPTIMIZATION TO JOB-SHOPSCHEDULING PROBLEM

A new heuristic algorithm is proposed for the problem of finding the minimum makespan in the job-shop scheduling problem. The new algorithm is based on the principles of particle swarm optimization (PSO). PSO employs a collaborative population-based search, which is inspired by the social behavior of bird flocking. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. By reasonably combining these two different search algorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, is developed. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated by applying it to some benchmark job-shop scheduling problems and comparing results with other algorithms in literature. Comparing results indicate that PSO-based a     

基于混合差分进化算法的并行机批处理调度问题研究

考虑到实际生产中产品多、批量小的特点,建立了一种带工艺约束的并行机批处理调度优化模型。为解决调度中的分批问题,提出了一种新的基于产品需求量的批量划分方案及批量染色体编码方式,采用两级差分进化算法来解决批量划分和批次调度问题;针对标准差分进化算法收敛速度慢、易出现早熟现象等问题,引入动态随机搜索和随机变异的局部搜索策略,以增强标准差分进化算法的局部搜索能力。测试算例及调度实例的仿真结果表明,该算法能有效地提高算法收敛速度,平衡其全局搜索和局部探索能力。     

基于激素调节机制改进型自适应粒子群算法在置换流水车间调度中的应用研究

研究以最小化最大流程时间为调度目标的离散型生产作业中的置换流水车间调度问题,将基于激素调节机制的改进型自适应粒子群算法应用到其中。在该算法中,粒子群算法的个体最优初始值不再是随机生成,而是由基于启发式信息的贪婪随机自适应算法得到的工件加工顺序转换而成,同时借鉴激素调节机制,引入激素调节因子,根据单个粒子周围的粒子的信息,对粒子的飞行方程进行改进,以提高搜索效率和搜索质量。对置换流水车间调度实例Rec系列基准问题进行测试,结果验证算法的有效性。     

基于粒子群优化的开放式车间调度

开放式车间调度(OSP)是重要的调度问题,它在制造领域中的应用非常广泛。优化调度算法是调度理论的重要研究内容。基于人工智能的元启发式算法是解决该问题的常用方法。分析了一种新的元启发式算法——粒子群优化(PSO)在信息共享机制上的缺陷,提出新的基于群体智能的信息共享机制。在该信息共享机制的基础上, 设计新的基于PSO的元启发式调度算法——PSO-OSP。该算法利用问题的邻域知识指导局部搜索,可克服元启发式算法随机性引起的盲目搜索。该算法应用于开放式车间调度问题的标准测试实例。仿真结果显示,PSO-OSP算法在加快收敛速度的同时提高了开放式车间调度解的质量。     

考虑节能的改进多目标樽海鞘群算法TFT-LCD面板阵列制程调度问题

TFT-LCD面板生产的阵列制程是可重入混合流水车间调度问题,采用一种改进多目标樽海鞘群算法对其进行优化求解。构建以最大完工时间、总拖期时间和总耗能为优化目标的数学规划模型;针对该问题结构特点,对基本多目标樽海鞘群算法进行了一系列改进操作,包括基于升序排列的随机键编码、PS方法解码、基于Lévy飞行的领导者个体位置更新方式,以及外部档案中非支配个体的变邻域搜索操作,并采用田口方法进行算法参数设置;最后通过对基准算例的数值实验,将改进多目标樽海鞘群算法与基本多目标樽海鞘群算法、多目标粒子群优化算法、快速非支配排序遗传算法进行对比,实验结果表明了改进多目标樽海鞘群算法的有效性。     

考虑批量装配的柔性作业车间调度问题研究

柔性作业车间调度是生产调度领域中的一个重要组合优化问题,由于取消了工序与加工设备的唯一性对应关系,因而相较于作业车间调度问题,具有更高的复杂度。针对该问题在批量装配方面的不足,考虑将批量因素与装配环节同时集成到柔性作业车间调度问题当中。以成品件的完工时间为优化目标,对该批量装配柔性作业车间调度问题进行了数学建模。针对该模型,提出一种多层编码结构的粒子群算法,并对该算法的各个模块进行了设计。最后,以实例验证了该数学模型的正确性及算法的有效性。     

带特殊工艺约束的双目标并行多机调度问题研究

港口的拖轮调度过程是一类带特殊工艺约束的并行多机调度问题.采用基于进化策略的混合算法,设计了基于工件的编码方式,对次序杂交算子进行了扩展,设计了一种扩展“倒位”变异算子,并采用相邻不同基因多次交换的局部搜索方法.算法的设计自动满足了工艺约束,保证了种群的多样性.设计了最大完工时间和生产加工成本双目标评价函数,最后通过计算对混合算法进行了验证.