（柔性）作业车间调度方法研究进展

车间生产过程中的调度问题是制造系统、运筹技术、管理技术与优化技术发展的核心，有效的调度方法与优化技术的研究和应用已成为先进制造技术实践的基础和关键。

作业车间调度（Job-shop Scheduling Problem，JSP）问题是NP-hard问题，求解十分困难。经典的FT 10问题，最早由Fisher等人在1963年提出，直到1988年才由Adams等人用瓶颈移动法首次求出其最优解930，时隔25年，其难度可见一斑。

数字制造装备与技术国家重点实验室高亮教授课题组致力于寻求高效的作业车间调度求解方法，并成功取得多项阶段性成果。如高亮、张国辉、张利平和李新宇提出了一种基于Memetic算法的求解方法。该方法基于关键路径，通过交换或插入关键块，设计了两种邻域结构并用于局部搜索，解决了调度算法易陷入局部最优解的难题。通过对国际通用的OR-Library标准测试集中的43个问题进行求解，计算出了33个问题的世界最好解。相关研究成果发表在Computers & Industrial Engineering（2011, 4, 699-705）上。

柔性作业车间调度问题（Flexible JSP，FJSP）是JSP问题的扩展，突破了JSP中一道工序只能在一台机器上加工的限制，使得能加工同一道工序的机器不唯一，在实际生产中，存在大量FJSP类型的车间。FJSP带来了很大的柔性，然而，因可选机器的引入，放宽了资源约束条件，扩大了寻优空间，在原本难以求解的JSP基础上又增加了求解难度，形成了新的挑战。

针对单目标柔性作业车间调度问题，数字制造装备与技术国家重点实验室的高亮、张国辉和石杨提出了一种基于改进遗传算法的求解方法。该方法采用了基于全局选择、局部选择和随机选择三种方法相混合的种群初始化方法，提高了初始种群中个体的多样性与质量，解决了随机初始解严重影响调度算法的寻优时间与寻优质量的难题。对国际通用的B&C标准测试集的21个问题进行求解，刷新了3个问题的世界最好解；对国际通用的D&P标准测试集的18个问题进行求解，刷新了11个问题的世界最好解。相关研究成果发表在Expert Systems with Applications（2011, 38, 3563-3573）上。

针对多目标柔性作业车间调度问题，数字制造装备与技术国家重点实验室的王晓娟、高亮、张超勇和邵新宇等人采用多目标优化理论与方法，提出了一种基于多目标遗传算法的求解方法。该方法采用免疫机制和熵原理维持进化种群的多样性，使得求出的Pareto解在数量和质量上具有明显的优势，解决了传统方法难以均匀求得较多Pareto解的难题。在对国际通用的Kacem标准测试集的4个问题进行求解，发现了3个新的Pareto最优解。相关研究成果发表在International Journal of Advanced Manufacturing Technology (2010, 50, 757-767 )上。

上述成果集中反映在高亮等人所著的《柔性作业车间调度智能算法及其应用》中。该书为“十二五”国家重点图书出版规划图书，获得国家科学技术学术著作基金资助，并于2013年10月获得第三届中国大学出版社图书奖优秀学术著作奖二等奖。

上述研究成果已成功应用于武昌造船厂的相关车间，如JSP算法主要用于武昌造船厂一分厂的机加车间，FJSP算法主要用于武昌造船厂特船部的管子加工车间，产生了显著的经济和社会效益。上述研究工作得到了国家自然科学基金项目（50305008, 60874075）的资助。

(供稿:高亮)