Abstract: 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 efficiency of TS procedure, the hybrid neighborhood structure which integrated swap and insertion operations was designed to enhance the scheduling solution. Through exchanging adjacent processing operation, neighborhood structure 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.

Key words: Job Shop, just in time scheduling, earliness/tardiness, tabu search, mathematical programming

摘要： 针对作业车间准时制生产调度这类典型的非正规性能指标调度问题，采用禁忌搜索和数学规划的混合策略进行求解，即在每一迭代搜索过程中，首先由禁忌搜索得到各机器上的工序加工序列，再调用数学规划方法来优化各工序的开工时间。另外，设计了一种包含交换和插入两种移动操作的邻域构造方法。邻域构造方法通过交换相邻加工工序对来在当前解的邻域内寻优，而将目标工序插入块之间的间隙以解除块对相关工序的束缚，这种邻域结构有助于提高禁忌搜索求解准时制生产调度问题的搜索效率。48个标准算例的仿真结果证明禁忌搜索/数学规划方法在准时制生产调度解的质量方面具有一定优势。

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