侍守创，江 浩，韩占港，蒋馨宙

(1.中国船舶重工集团公司第七一六研究所，江苏 连云港 222002；2.哈尔滨工程大学计算机科学与技术学院，黑龙江 哈尔滨 150001)

1 引言

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem，FJSP)是一类满足任务配置需求和顺序约束要求的组合优化问题，属于NP-hard范畴[1]。

近年来，针对FJSP问题，国内外学者进行了许多相关研究，并取得了一些成果。目前代表性研究方法有粒子群算法、遗传算法、邻域搜索算法等，同时学界提出可采用启发式算法如禁忌搜索算法[2]、模拟退火算法[3]、遗传算法[4]以及蚁群算法[5]等解决该问题。魏巍等人[6]以加工质量、加工成本和加工工期为多目标，并采用一种改进的Pareto算法进行优化，缺陷是不适合数据规模较大的问题，并且FJSP是NP-hard问题，其求解时间随着数据规模增大而迅速增长，而近似方法可以在确定时间内得到一个较优解。针对FJSP的求解方法大致分为精确方法和近似方法两类，精确方法适用于小规模FJSP问题，当问题规模增大时，便不再适用[7]。基于智能优化算法的解决方案能够在可行时间内求得大规模FJSP问题的近优解，现已成为解决柔性作业车间调度问题的主流方法以及研究热点。Xia和Wu[8]提出了使用粒子群和模拟退火相结合的方式来解决FJSP，但是多次运行结果方差较大，不能有效得到一个较优解。Fattah和Mehrabad[9]提出一个数学模型并采用禁忌搜索和模拟退火算法来解决实际生产环境中的作业调度问题，然而对约束情况较多、情况较复杂的柔性作业车间问题解决能力差。……