工件有到達(dá)時(shí)間排序問(wèn)題的LS算法分析

    排序問(wèn)題是組合優(yōu)化領(lǐng)域中的一類重要問(wèn)題，它是利用一些處理機(jī)、機(jī)器或者資源，最優(yōu)地完成一批給定的任務(wù)或作業(yè)，在生產(chǎn)管理與調(diào)度、網(wǎng)絡(luò)通信、理論計(jì)算機(jī)科學(xué)等方面有廣泛的應(yīng)用。 本文主要研究在m臺(tái)同型機(jī)上工件有到達(dá)時(shí)間的排序問(wèn)題的LS算法。目標(biāo)函數(shù)是使機(jī)器的最大完工時(shí)間（makespan）達(dá)到最小。 第一章介紹了排序問(wèn)題，算法的競(jìng)爭(zhēng)比分析等基本概念，描述了（半）在線排序和工件有任意到達(dá)時(shí)間的在線排序模型的一些特性。第二章研究了m臺(tái)同型機(jī)上有到達(dá)時(shí)間工件的LS排序問(wèn)題，研究了LS算法的最壞性能比。給出了LS算法的緊性能比的一個(gè)簡(jiǎn)單證明。第三章討論了m臺(tái)同型機(jī)上工件有到達(dá)時(shí)間且加工時(shí)間非增的LS算法問(wèn)題，得到如下的兩個(gè)結(jié)論，一個(gè)是證明了對(duì)于任意工件序列L={J1，J2，…，Jn）如果 r1≤r2≤…≤rn且P1≥P2≥…≥Pn，有R（m，LS）≤3/2-1/2m；另一個(gè)是若到達(dá)時(shí)間為任意的且加工時(shí)間為單調(diào)非增序列，則LS算法的最壞性能比不大于2。
 

請(qǐng)繼續(xù)閱讀相關(guān)推薦：畢業(yè)論文    應(yīng)屆生求職

畢業(yè)論文范文查看下載      查看的論文開題報(bào)告     查閱參考論文提綱

查閱更多的畢業(yè)論文致謝    相關(guān)畢業(yè)論文格式       查閱更多論文答辯

【工件有到達(dá)時(shí)間排序問(wèn)題的LS算法分析】相關(guān)文章：

與誤工有關(guān)的多目標(biāo)排序問(wèn)題11-18

最小邊排名問(wèn)題的若干算法研究12-04

教育失敗問(wèn)題分析論文03-04

兩類雙目標(biāo)排序問(wèn)題研究論文提綱11-18

最小邊排名問(wèn)題的若干算法研究寫作提綱12-05

酒店管理服務(wù)問(wèn)題分析論文03-02

企業(yè)員工培訓(xùn)問(wèn)題與對(duì)策分析03-27

分析物流企業(yè)成本控制問(wèn)題11-29

企業(yè)成本核算問(wèn)題分析03-29