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

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

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

畢業(yè)論文范文查看下載      查看的論文開(kāi)題報告     查閱參考論文提綱

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

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

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

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

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

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

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

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

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

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

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