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

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

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

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



本文編號(hào)：3794992