关键词: 作业车间调度, 提前/拖期惩罚, 不同交货期, 解码, 粒子群算法

Abstract: Aiming at the Job Shop earliness and tardiness scheduling problem with informal performance index, a new decoding method with three hierarchical structure applied to particle and chromosome was designed based on procedure code pattern. A semi-active decoding operation was employed to extend the search band of initial scheduling solution. The active scheduling method of insert greedy decoding was used for the tardy jobs to reduce the tardiness cost of jobs. The active decoding operator with reversal mechanism was operated to delay the due date of all parts, and the premature punishment cost was reduced further on the premise of tardy jobs completion time unchanged. Thus, the total tardiness and earliness costs could be cut down owing to these three successive decoding procedures. This method was applied to particle decoding in Particle Swarm Optimization (PSO), and the iterative optimization of scheduling solution was realized by updating the particle position. The effectiveness of the method was improved by simulation result of 120 random scheduling examples.

Key words: Job Shop scheduling, earliness/tardiness punishment, distinct due date, decoding, particle swarm optimization