工件有到達時間排序問題的LS算法分析

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

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

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

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

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

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

最小邊排名問題的若干算法研究12-04

教育失敗問題分析論文03-04

兩類雙目標排序問題研究論文提綱11-18

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

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

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

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

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