关键词: 平行机, 分批, 调度, 准备时间, 到达时间, 交货期, 遗传算法, 模拟退火算法

Abstract: A kind of integrated batch planning and parallel machine scheduling problems which constraint order's due time, arrival time and setup time were studied. Aiming to reduce the manufacturing costs and tardiness penalty costs, a single mathematical model was constructed to describe the integration problem. A genetic-simulated annealing algorithm with heuristic rules was proposed. The heuristic rules were introduced to shorten the length of chromosome and increase the searching speed. Genetic algorithm was used to conduct global search for based batch. On the premise of batch determination, the batch optimal scheduling was obtained by using annealing algorithm. Under the same computing time, computational simulations and comparisons based on five kinds of application cases with different sizes were provided. Results demonstrated that the advantage of proposed algorithm became more obvious with the task scale increased. Thus the effectiveness and feasibility of proposed method and algorithm for these kind of special problems were illustrated.

Key words: parallel machine, batch, scheduling, setup time, arrival time, due date, genetic algorithms, simulated annealing algerithms