摘要
研究确定性排序理论的一个新模型：考虑４台机器的集合Ｍ＝（Ｍ１，Ｍ２，Ｍ３，Ｍ４）和ｎ个零件的集合Ｊ＝（ｊ１，ｊ２，…，ｊｎ），每个零件同时被２ｉ＝（ｉ＝０，１，２）台机器同时加工。证明了在不允许间断，优化指标为作业排序长度的条件下，该问题是强ＮＰ－完全问题，没有多项式时间算法。
This paper is concerned with a new model in deterministic scheduling problem where some tasks may be executed by more than one processor at a time.We consider a set M which is consisted of processors m 1,m 2,m 3,m 4 and another set J which is composed of tasks J 1,J 2,…,J n .We have showed that scheduling problem P 4|fix,2 i | C max is NP complete problem there does not exist polynomial time algorithm.
关键词
复合并行机排序
计算复杂性
排序问题
scheduling multi processor tasks
computational complexity
NP complete problem
strong NP complete problem
