在這篇論文中,我們主要討論了具有相似加工時間且加工時間非遞增的工件在2臺同類型平行機上的離線加工排序問題,分析了LPT算法的最壞性能比.其目標(biāo)函數(shù)是要令所有機器的最大完工時間達到最小.若工件序列L= {J1,J2,…,Jn}中的工件滿足pj∈[1,r](r ≥ 1)且P1≥p2 ≥…≥pn,當(dāng)m = 2時,證明了LPT算法的最壞性能比為(?)當(dāng)11/8≤ r ≤3/2時,我們得到的性能比和文章[1]的結(jié)果一樣.當(dāng)r<11/8時,我們得到的最壞性能比比文章[1]的結(jié)果更小且是緊的.文章的第一章為緒論,介紹了閱讀本文所需要的預(yù)備知識和基本概念,包括組合優(yōu)化問題,近似算法,排序問題,LS以及LPT算法.文章的第二章,證明了具有相似加工時間且加工時間非遞增的工件,在2臺同類型平行機上的LPT算法的最壞性能比.文章的第三章,我們總結(jié)了整篇文章以及對未來工作的建議.

【文章頁數(shù)】：31 頁

【學(xué)位級別】：碩士

【文章目錄】：
中文摘要
英文摘要
第一章 緒論
    1.1 組合優(yōu)化問題及近似算法簡介
    1.2 排序問題簡介
    1.3 在線、離線及半在線問題
    1.4 LS及LPT算法簡介
第二章 兩臺機器上LPT算法性能分析
    2.1 引言
    2.2 引入的符號
    2.3 定理及其證明
第三章 小結(jié)
參考文獻
致謝



本文編號：3794992