需要安装时间的两台多功能机排序问题的计算复杂性  

The Computational Complexities of Two Multi-purpose Machines Scheduling Problem with Setup Times

作　　者：井彩霞[1] 钱省三[1] 唐国春[2] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]上海第二工业大学经济管理学院,上海201209

出　　处：《运筹学学报》2008年第4期122-128,共7页Operations Research Transactions

基　　金：国家自然科学基金(10371071，70731160015)资助;上海市(第三期)重点学科资助(编号：S30504)资助

摘　　要：提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.This paper proposes multi-purpose machine scheduling problems with setup times. Generally, they are NP-hard. We mainly study the computational com- plexities of several special cases on two machines. Polynomial algorithm and branch and bound algorithms are given for different number of job groups whose processing set con- tain both machines. For the case that all the job groups have the same number of jobs and equal processing times, we give a polynomial time optimal algorithm-parity algorithm, and thereby prove that the problem is polynomial.

关 键 词：运筹学  排序  计算复杂性  多项式时间算法  多功能机  安装时间 

分 类 号：O223[理学—运筹学与控制论] TP301.5[理学—数学]