运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2008年
4期
122-128
,共7页
运筹学%排序%计算复杂性%多项式时间算法%多功能机%安装时间滗
運籌學%排序%計算複雜性%多項式時間算法%多功能機%安裝時間潷
운주학%배서%계산복잡성%다항식시간산법%다공능궤%안장시간필
提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都 相等的情况,给出一个多项式时间的最优算法一奇偶算法,从而证明此问题是多项式时间可解的.
提齣需要安裝時間的多功能機排序問題,一般情況下,這是NP-睏難的;主要研究隻有兩檯機器時一些特殊情況下的計算複雜性.根據加工集閤為機器全集的工件組數的不同,分彆給齣多項式時間算法和分枝定界算法.對各工件組的工件數和加工時間都 相等的情況,給齣一箇多項式時間的最優算法一奇偶算法,從而證明此問題是多項式時間可解的.
제출수요안장시간적다공능궤배서문제,일반정황하,저시NP-곤난적;주요연구지유량태궤기시일사특수정황하적계산복잡성.근거가공집합위궤기전집적공건조수적불동,분별급출다항식시간산법화분지정계산법.대각공건조적공건수화가공시간도 상등적정황,급출일개다항식시간적최우산법일기우산법,종이증명차문제시다항식시간가해적.
