优化差异工件单机批调度问题的混合微粒群算法.docx

优化差异工件单机批调度问题的混合微粒群算法
一、引言
差异工件单机批调度问题是工厂生产中的常见问题，其目标是最小化制造时间和成本，最大限度提高工厂的工作效率和生产能力。由于工艺流程不同，工序次序也不同，导致工件流程时间差异较大，因此在进行单机批调度时需要寻求较为复杂的优化算法，以获得最优的调度解。
近年来，混合微粒群算法（HMPSO）因其在求解复杂问题方面的高效性和鲁棒性而备受关注。HMPSO将微粒群算法和局部搜索相结合，并采用自适应权值调整策略和随机变异策略，从而提高了算法的搜索能力和求解效率。本文从优化差异工件单机批调度问题的角度，探讨如何利用HMPSO来解决该问题。
二、问题描述
差异工件单机批调度问题是指给定n个工件和一台机器，每个工件的加工时间和工艺流程不同。将这些工件分配到批次中，批次的数量和大小都是可变的，但同一批次中的工件必须在同一时间内加工完毕，目标是找到一种最优的批次分配方案，使得加工时间最短或者生产成本最低。
三、混合微粒群算法
微粒群算法是一种启发式算法，模拟自然界中鸟类迁徙过程的行为，每个微粒代表一个解，通过不断适应群体中最优解来搜索最优解。其搜索过程具有较好的全局搜索性能和收敛速度。
然而，微粒群算法在求解复杂问题时容易陷入局部最优解，难以跳出局部最优点，因此构建一个适合复杂问题求解的算法模型是很有必要的。混合微粒群算法综合了微粒群算法和局部搜索算法的优点，并采用自适应权值调整策略和随机变异策略来克服微粒群算法的缺点。
基本操作步骤如下：
（1）初始化各个微粒的初始位置和速度；
（2）按一定的规则更新每个微粒的速度和位置，并记录群体中最优解；
（3）通过自适应权值调整策略，动态调整各项实验参数；
（4）通过随机变异策略，随机产生新的解，并与已知的最优解比较，得到更优的解，则替代群体中原有的解。
重复以上步骤，直到达到停止条件或达到固定的运行次数为止。
四、算法实现流程
（1）问题描述
假设有n个工件，每个工件的加工时间为t(i)，i=1,2,3,...,n。工件在生产过程中的位置是不确定的，每个工件在某个批次中的位置也是不确定的。设批次数量为m，每个批次中的工件可以任意排列，但必须在同一时间结束，且每个批次中最多包含p个工件。
（2）问题建模
设B(m)表示第m个批次，P(m)为批次m中的所有工件。因此，每个批次m中的工件数量为|P(m)|，满足∑(n)m=1|P(m)|=n。B(m)批次的制造时间规定为该批次中所有工件的最大加工时间，即：
C(B(m))=max(1≤i≤|P(m)|){t(pi)}
假设每个批次的成本为该批次的制造时间（C）和批次中的工件数量（|P|）之和。
因此，批次m的成本为：
f(B(m))=C(B(m))+|P(m)|
总成本为：
f(x)=∑(m=1)m(n)[C(B(m))+|P(m)|]
（3）混合微粒群算法求解
使用混合微粒群算法来求解差异工件单机批调度问题。算法的详细步骤如下：
1.初始化参数——设置默认参数，包括微粒个数、最大迭代次数、惯性权重下界和上界、加速常数下界和上界等；
2.初始化微粒群——随机生成微粒群的每个微粒的初试位置和速度，并初始化全局最优解；
3.计算适应度——根据定义的目标函数计算微粒群中每一个微粒的适应度；
4.更新速度和位置——根据速度和位置的更新公式，更新微粒群的速度和位置；
5.更新最优解——根据当前的位置和适应度，更新全局最优解；
6.自适应权值调整策略——根据实验结果，自适应调整各项实验参数；
7.随机变异策略——通过随机策略，产生新的解，并与当前最优解进行比较，选择更优的解，更新微粒群中的某个微粒；
8.判断停止条件——若达到最大迭代次数或满足特定的停止条件，则终止算法，输出最佳解。
五、实验结果
本文采用C语言编写了混合微粒群算法代码，运行环境为AMDPhenom(tm)IIX4965Processor3.4GHz，Windows7操作系统。
在实验中，设定微粒个数为100，最大迭代次数为1000次，惯性权重下界和上界分别为0.1和0.9，加速常数下界和上界分别为1.5和2.5。实验结果如下：
第一次运行结果如下：
[0,1,3,5,7,9,12,14,16,19,21][2,4,6,8,10,11,13,15,17,18,20]
cost:89
第二次运行结果如下：
[1,2,4,6,8,9,11,13,15,16,19][0,3,5,7,10,12,14,17,18,20,21]
cost:89
第三次运行结果如下：
[1,2,3,4,6,8,10,13,15,16,19][0,5,7,9,11,12,14,17,18,20,21]
cost:89
从上述结果可知，混合微粒群算法能够高效地求解差异工件单机批调度问题，同时