关键词: 同类机, 批调度, 蚁群优化算法, 组合优化, 启发式算法

Abstract: To improve the production efficiency by using batch processor effectively, a batch scheduling problem with non-identical job size on uniform parallel machines was proposed and solved. This problem was proved to be NP-hard, thus a lower bound was presented to evaluate the performance of approximation algorithms, and the validity of this lower bound was proved. On the basis of recessive processing time concept, a new local optimization algorithm was proposed to improve the max-min ant algorithm. A heuristic algorithm named Longest Processing Time for Uniform Machines (LPTUM ) was used to solve the problem. Through simulation experiment, the proposed algorithm was compared to genetic algorithm, particle swam optimization and BFLPT, as well as the performance was analyzed.

Key words: uniform parallel machines, batch scheduling, ant colony optimization, combinatorial optimization, heuristic algorithms