摘要
提出需要安装时间的多功能机排序问题,一般情况下,这是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.
出处
《运筹学学报》
CSCD
北大核心
2008年第4期122-128,共7页
Operations Research Transactions
基金
国家自然科学基金(10371071,70731160015)资助
上海市(第三期)重点学科资助(编号:S30504)资助
关键词
运筹学
排序
计算复杂性
多项式时间算法
多功能机
安装时间
Operations research, scheduling, computational complexity, polynomial algorithm, multi-purpose machine, setup time