工件有到達時間排序問題的LS算法分析
排序問題是組合優化領域中的一類重要問題，它是利用一些處理機、機器或者資源，最優地完成一批給定的任務或作業，在生產管理與調度、網絡通信、理論計算機科學等方面有廣泛的應用。 本文主要研究在m臺同型機上工件有到達時間的排序問題的LS算法。目標函數是使機器的最大完工時間（makespan）達到最小。 第一章介紹了排序問題，算法的競爭比分析等基本概念，描述了（半）在線排序和工件有任意到達時間的在線排序模型的一些特性。第二章研究了m臺同型機上有到達時間工件的LS排序問題，研究了LS算法的最壞性能比。給出了LS算法的緊性能比的一個簡單證明。第三章討論了m臺同型機上工件有到達時間且加工時間非增的LS算法問題，得到如下的兩個結論，一個是證明了對于任意工件序列L={J1，J2，…，Jn）如果 r1≤r2≤…≤rn且P1≥P2≥…≥Pn，有R（m，LS）≤3/2-1/2m；另一個是若到達時間為任意的且加工時間為單調非增序列，則LS算法的最壞性能比不大于2。
【工件有到達時間排序問題的LS算法分析】相關文章：
與誤工有關的多目標排序問題11-18
最小邊排名問題的若干算法研究12-04
教育失敗問題分析論文03-04
兩類雙目標排序問題研究論文提綱11-18
最小邊排名問題的若干算法研究寫作提綱12-05
酒店管理服務問題分析論文03-02
企業員工培訓問題與對策分析03-27
分析物流企業成本控制問題11-29
企業成本核算問題分析03-29
- 相關推薦