万婧

(山东省科学院海洋仪器仪表研究所，山东省海洋仪器仪表科技中心，山东 青岛 26600)

求解可重入作业车间调度问题的改进离散微粒群优化算法

万婧

(山东省科学院海洋仪器仪表研究所，山东省海洋仪器仪表科技中心，山东 青岛 26600)

本文针对可重入作业车间调度问题，对离散微粒群算法的搜索方式进行改进，混合一种变异机制，并结合Interchange邻域局部搜索机制，设计与开发有效的混合离散微粒群算法。通过实验仿真结果的比较，有力地证明了所提算法的有效性。

离散微粒群算法；局部搜索；作业车间

可重入作业车间调度问题(reentrant job shop scheduling problem，RJSP)是工业生产中的典型调度问题，是现代很多实际生产调度问题的简化模型，包括诸如半导体生产、超大规模集成电路设计与制造、物流运输、网络通信电路设计、电气布线等问题。可重入作业车间调度问题的求解难度很高，一直是学术界和工程界共同关注的重要课题。除混合的算法开发外，设计新颖的调度技术或将其他领域的优化算法推广到生产调度问题中同样是值得关注的课题。

1 问题模型

可重入作业车间调度问题通常描述如下：每个工件i在m台机器上要被加工R(i)次，R(i)是可变的；所有工件经过机器的顺序都是恒定的；任何时刻，每台机器只能加工一个工件，每个工件也只能在一台机器上进行加工。

C(πj,1,l(πj))=max{C(πj-1,1,l(πj-1)),C(πj,m,l(πj)-1)}+p(πj,1,l(πj)),j=1,…,R,

C(πj,k,l(πj))= max{C(πj-1,k,l(πj-1)),C(πj,k-1,l(πj))}+p(πj,k,l(πj)),k=2,…,m,

Cmax(π)=C(πR,m,l(πR)),

π*=arg{Cmax(π)}→min,

式中：m表示机器数，R表示n个工件中每个工件的重入次数，n表示工件数，π=[π1,π2,…,πR]是工件加工排序，πj∈{1,…,n}(j=1,…,R)表示排序π中第j个位……