王艳红,赵也践,刘文鑫

(沈阳工业大学 人工智能学院,辽宁 沈阳 110870)

0 引言

车间调度在生产制造中扮演着重要的角色,一直是控制科学和制造领域的研究热点。作业车间调度问题(Job Shop Scheduling Problem,JSSP)是车间调度领域中的经典案例,具有NP-Hard特性[1],即难以通过遍历所有可行解来获得最优解。传统的JSSP优化方法分为最优化方法和近似优化方法两大类。最优化方法能够获得JSSP的最优解,这类方法包括数学规划法(mathematical programming)、分支定界法(branch and bound)和枚举法(enumerative methods)等,然而这些方法只能求解小规模JSSP案例,随着算例规模的不断增大,可行解空间的规模会以指数形式增大,而遗传算法(Genetic Algorithm,GA)[2]、粒子群优化(Particle Swarm Optimization,PSO)算法[3]等经典的近似优化方法虽然可以求取大规模JSSP的近似最优解,但是存在耗费时间更多和需要反复调参等缺陷。

随着信息技术的发展与应用,车间在生产中积累了越来越多的离线或在线生产数据,这些数据中隐藏着大量可以反映和指导求解JSSP的调度信息,如果能够高效利用这些生产数据,并使用某些技术提取出可靠的调度知识来提高调度算法的优化能力,则可提高作业车间的加工效率。传统的数据处理与分析技术在处理当今海量数据时具有局限性。数据挖掘(Data Mining,DM)技术打破了这些瓶颈,使用DM技术从离线数据中获取隐含在加工过程中的有效调度知识来分析与优化调度算法,进而指导作业车间的调度过程,成为一种求解JSSP的新思路。同时,这些调度知识能够保留并增强原有调度算法的优化能力,生成更加接近最优解的较优调度策略,在JSSP调度过程中具有重要的意义。……