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

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