关键词: 排序, 多功能机, 双目标, 启发式算法

Abstract: A multi-purpose machine scheduling problem with bicriteria and setup times is discussed. In which jobs can be processed by any machine of a prespecified subset of the machine set, moreover, jobs are divided into different groups and a changeover time is required whenever there is a switch from processing a job of one group to another job of a different group. Objective function of this problem is to minimize makespan and total times of setup. Style of the bicriteria scheduling problem is established according to the background of practical application. As the problem is proved to be NP-hard, a heuristic which provides heuristic efficient solutions is presented. In the heuristic, dispatch all the job groups to machines according to specific rules firstly, then a series of heuristic efficient solutions can be achieved by improving the makespan and splitting the job groups gradually. Extensive computational experiments indicates the feasibility and effectiveness of this heuristic algorithm.

Key words: scheduling, multi-purpose machine, bicriteria, heuristic algorithm