金 花 宁 涛 刘 芳

(大连交通大学软件学院,辽宁 大连 116045)

多目标FJSP包括机器分配和工序排序两个子问题。吴俊和方锦明提出基于禁忌算法利用分步策略求解FJSP的两个子问题[2]。Chaudhry I A在考虑机器负荷平衡性的前提下，提出了一种选择累加工时较短机器的机器选择法，虽然这种方法提高了初始种群的质量，但增加了机器选择的复杂性[3]。刘晓冰等提出了包括机器选择链和工序顺序链的双链量子编码方法，但该方法对机器选择对工序顺序的影响考虑较少[4]。Deng G L和Gu X S提出了一种混合的离散差分进化算法求解非空闲置换流水车间调度问题，该算法用一种基于网络表示的加速方法对工件加工序列的邻域进行评价[5]。Mokhtari H等为了优化最大完工时间和总成本双目标，采用混合了可变邻域搜索和坐标方位搜索的DE算法，但他们对影响算法效率的因素分析不充分[6]。

笔者在分析FJSP的特点并总结已有文献方法优势和不足的基础上，提出利用模拟细菌觅食行为的改进细菌觅食算法(Improved Bacteria Foraging Optimization Algorithm,IBFOA)来求解FJSP[7]。

1.1 问题描述

FJSP的描述如下：车间有N个待加工工件并配有M台机器，每个工件i(i∈{1,2,…,N})包含ni(ni≥1)道工序，工序要按照指定的加工路线进行；Rij表示工件i的第j(j∈{1,2,…,ni})道工序，Mij(Mij⊆{1,2,…,M})表示可以加工工件i的第j道工序的机器集合，每道工序Rij可以在M台机器中有处理能力的任意一台机器m(m∈{1,2,…,Mij})上加工，机器m可以加工不同工件的多道工序[8,9]。问题包括机器选择和工序排序两个子问题。

1.2 目标函数

生产企业实现效益的首要目标是及时、高效地完成生产任务，因此FJSP首要的调度目标是最小化最大完工时间和最小化总成本。……