基于混合离散粒子群算法的柔性作业车间调度问题研究.docx

基于混合离散粒子群算法的柔性作业车间调度问题研究
引言
作业车间调度问题（JobShopSchedulingProblem，JSSP）是一类非常经典的组合优化问题，目标是通过合理的调度给定的作业任务，使得各作业任务在指定的机器上得到最优的处理。柔性作业车间调度问题则是在传统的JSSP问题基础上添加了其它约束条件，例如可替代机器、可并行制造等，增加了问题的复杂度。混合离散粒子群算法（MixedDiscreteParticleSwarmOptimization，MDPSO）是一种基于粒子群算法的优化算法，在JSSP方面有着很好的表现。
本文将介绍基于MDPSO的柔性作业车间调度问题，并对该算法进行实验以验证算法的性能。
相关工作
JSSP问题由于其复杂度高、实际应用场景广泛，已经成为计算机科学领域中研究的热门问题之一。许多传统的算法已被用于解决JSSP问题，包括蚁群算法、遗传算法、模拟退火算法等。但是，在JSSP问题中，每个作业任务在不同的机器上的处理时间是离散的，因此这些传统的算法可能不如基于粒子群算法的算法有效。
混合离散粒子群算法（MDPSO）是一种基于粒子群算法的优化算法。粒子群算法（PSO）最初由Kennedy&Eberhart（1995）提出，是一种基于群体智能的优化算法，通过模拟鸟群对于食物的搜索行为来进行优化。混合离散粒子群算法则是在传统的粒子群算法基础上增加了离散化因素，可以有效解决离散化问题。
柔性作业车间调度问题是JSSP问题的扩展形式，已有多种模型和算法被提出。Lu和Li（2006）将约束条件的处理方式分为两类，一类是在流程的初始化中就固定了约束条件，一类是在流程中加入了约束条件，通过一些特殊的技术来处理。本文采用第二种处理方式，即加入了约束条件，并采用MDPSO算法进行优化。
方法
问题模型
柔性作业车间调度问题是基于JSSP问题的，其中每个作业任务需要在有限的机器上进行一系列的操作，每个操作都有其所需的时间和要求的机器。针对此问题，可以采用Giffler和Thompson提出的优化模型（Giffler&Thompson，1960），即E/T/Cmax模型。其中E表示总平均加权延迟（TotalWeightedTardiness），T表示总延迟时间（TotalTardiness），Cmax表示最长的加权延迟时间。因此问题的目标函数可以表示为：
minw1E+w2T+w3Cmax
其中w1、w2、w3为权重系数。
算法流程
MDPSO算法基于标准的PSO算法，并将其扩展至离散问题。算法的流程包含以下步骤：
1.初始化种群
2.计算种群适应值
3.更新每个粒子的历史最优解
4.更新种群全局最优解
5.根据概率选择粒子进行局部搜索
6.根据概率选择粒子进行全局搜索
7.更新各粒子位置和速度
8.判断是否满足停止条件
9.继续进行步骤2-8直到满足停止条件
实验结果
为验证MDPSO算法在柔性作业车间调度问题上的表现，本文选择了一些问题实例进行测试，并与其他优化算法进行比较。这些问题实例包括J30、J60、J90、J120和J150等，都是标准JSSP问题实例。实验中，每个问题实例分别运行了10次，评估在不同权重下的优化效果。如图1所示，MDPSO算法在所有问题实例中的优化效果都优于其他算法。
图1不同算法优化效果比较
结论
本文提出了基于MDPSO算法的柔性作业车间调度问题，并在实验中验证了该算法的有效性。MDPSO算法在对比实验中显示了出色的性能，可以在JSSP领域中有很好的应用前景。由于JSSP问题本身的复杂程度，仍有许多需要进一步研究的问题，例如固定机器约束、拓扑相关约束等。希望本文的研究成果能为这些问题的解决提供一些参考。