TS/MP混合算法求解作业车间JIT调度问题  

Tabu search and mathematical programming for just-in-time Job Shop scheduling

作　　者：李海宁[1] 孙树栋[1] 杨宏安[1] 

机构地区：[1]西北工业大学机电学院,陕西西安710072

出　　处：《计算机集成制造系统》2012年第6期1176-1181,共6页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(50705076;51075337)~~

摘　　要：针对作业车间准时制生产调度这类典型的非正规性能指标调度问题,采用禁忌搜索和数学规划的混合策略进行求解,即在每一迭代搜索过程中,首先由禁忌搜索得到各机器上的工序加工序列,再调用数学规划方法来优化各工序的开工时间。另外,设计了一种包含交换和插入两种移动操作的邻域构造方法。邻域构造方法通过交换相邻加工工序对来在当前解的邻域内寻优,而将目标工序插入块之间的间隙以解除块对相关工序的束缚,这种邻域结构有助于提高禁忌搜索求解准时制生产调度问题的搜索效率。48个标准算例的仿真结果证明禁忌搜索/数学规划方法在准时制生产调度解的质量方面具有一定优势。Aiming at the Just-In-Time （JIT） Job Shop scheduling problem with earliness and tardiness penalties, a combination of Tabu Search （TS） and Mathematical Programming （MP） procedure was used to find solutions. In each iterative search process, the sequences of operations on the machines were produced by TS procedure, and the completion times of operations belonged to the generated sequences was optimized by MP. To improve the search ef- ficiency of TS procedure, the hybrid neighborhood structure which integrated swap and insertion operations was de- signed to enhance the scheduling solution. Through exchanging adjacent processing operation, neighborhood struc- ture method could optimize in neighborhood of current solution. The objective process was inserted in gap to get off the relate process. This neighborhood structure could improve the search efficiency of JIT production scheduling in TS. The simulation results of 48 standard examples showed that TS/MP method had advantages in quality of JIT production scheduling.

关 键 词：作业车间 准时制调度 提前/拖期 禁忌搜索 数学规划 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]