中文摘要：

讨论了双目标函数下需要安装时间的平行多功能机排序问题。在该问题中,每个工件对应机器集合的一个子集,且每个工件只能在相应子集中的任一台机器上加工,工件分组,不同组中的工件连续加工需要安装时间,目标函数为极小化最大完工时间和安装次数。根据实际应用背景确定双目标排序问题的形式,并证明了该问题是NP—难的。设计了一个求启发式有效解的算法,首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后逐步改进最大完工时间和拆分工件组,从而得到一系列的启发式有效解。实验表明,该算法是实用而有效的。

英文摘要：

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.