运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2007年
3期
65-74,94
,共11页
运筹学%近似算法%幺模矩阵%分支定界%列生成算法%NP-困难
運籌學%近似算法%幺模矩陣%分支定界%列生成算法%NP-睏難
운주학%근사산법%요모구진%분지정계%렬생성산법%NP-곤난
在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|tij,rj|∑wjCj是有效的.
在求解大規模NP-睏難的最優化問題方法中,列生成技術越來越受到重視.本文研究工件帶有與加工次序有關的安裝時間的單機排序問題,首先構造它的時間標號模型,結閤D-W分解技術和分支定界方法,給齣它的列生成算法.其中時間標號模型的線性鬆弛為原問題提供瞭很好的下界,然後提齣一箇近似算法.通過實驗數據錶明,我們的算法對中等規模的排序問題1|tij,rj|∑wjCj是有效的.
재구해대규모NP-곤난적최우화문제방법중,렬생성기술월래월수도중시.본문연구공건대유여가공차서유관적안장시간적단궤배서문제,수선구조타적시간표호모형,결합D-W분해기술화분지정계방법,급출타적렬생성산법.기중시간표호모형적선성송이위원문제제공료흔호적하계,연후제출일개근사산법.통과실험수거표명,아문적산법대중등규모적배서문제1|tij,rj|∑wjCj시유효적.
