流水車間與開放車間調度算法漸近分析

內容簡介

流水車間與開放車間調度算法漸近分析是一本介紹流水車間與開放車間調度在流程工業、離散製造、檢測維修以及醫療管理等領域，本書的部分研究成果是作者與東北大學唐立新教授、清華大學張智海副教授合作完成的.

是國家自然科學基金青年科學基金項目(71201107)的資助與支持.在本書的撰寫過程中，東北大學軟體學院碩士研究生唐夢倩、張強、劉冰倩、趙鵬做了大量的工作；在本書的出版過程中，得到了清華大學出版社責任編輯的支持和幫助。

本書可作為系統工程、套用數學、運籌學與控制論、計算機軟體與理論、工業工程、管理科學與工程等相關專業的教師、研究生、高年級本科生以及科研人員的參考書.

流水車間與開放車間調度在流程工業、離散製造、檢測維修以及醫療管理等領域有著廣泛的套用.除了極少數特殊情況之外，此類問題基本上都是NP難的.對於小規模問題，一般是採用基於枚舉的算法進行最優求解.但是隨著問題規模的增大，求得最優解所花費的時間成指數增長，在這種情況下，利用啟發式算法求得問題的近似解是一種快速而有效的方法.本書針對所研究的車間調度模型，從理論的角度分析了若干典型啟發式算法的性能，其中重點討論了漸近分析方法在研究調度算法收斂性方面的套用.

前言

車間調度模型源自現代化工業生產過程，是複雜的多階段決策過程，所研究的問題是確定若干項任務在一組處理機上的開始時間和加工順序，使得目標函式最最佳化.在這些問題中，絕大多數都是NP難的，即此類問題無法在多項式時間內求得最優解.對於小規模問題，一般是套用分支定界或動態規劃等枚舉算法進行最優求解.但是隨著問題規模的增大，求得最優解所花費的時間成指數增長，此時，人們往往放棄尋求問題的最優解，轉而尋找一個可以快速求得的可行解，把它作為最優解的近似值.通常，這樣的近似解可以通過構造啟發式算法而得到.那么，如何從理論角度評價啟發式的有效性（即近似解的優劣）呢？經典的方法就是研究算法的目標函式值與該問題（離線）最優值之間的最大誤差，以此來大致描述啟發式的性能，稱之為最壞情況（競爭）分析.但是，用該方法求得的算法最壞情況（競爭）比緊界，都是一些人為構造的、極其特殊的實例，在大規模工業生產環境中發生的機率為零.為了描述算法在求解大規模問題時的性能，較為合適的方法是採用漸近性能（競爭）分析，研究極限狀態下，算法的目標函式值與該問題（離線）最優值之間的接近程度.若算法的漸近性能（競爭）比為1，則稱之為漸近最優算法，即在理想狀態下（問題規模趨於無窮大）可以將其看作是最優算法.

儘管漸近分析方法在評價啟發式算法的收斂性方面有著無可比擬的優勢，但是國際上的相關成果卻並不多見.本書是作者近年來相關科研成果的總結，其中融合了多篇在國外期刊上發表的科研論文，重點討論流水車間和開放車間調度算法的漸近分析，同時也對其中的一些算法進行了最壞情況（競爭）分析.全書共分為10章，主要內容概括如下：第1章為緒論，簡要介紹調度問題的描述與求解方法、算法性能分析方法以及相關問題研究現狀；第2~3章介紹流水車間極小化最大完工時間問題，證明了基於“單工件優先”啟發式算法的漸近最優性，並提出了新的問題下界；第4~6章介紹了流水車間極小化完工時間k次方和問題，證明了基於“最短加工時間優先”啟發式算法的漸近最優性，並進行了最壞情況（競爭）分析，提出了新的問題下界；第7~8章介紹了開放車間極小化最大完工時間問題，分別證明了“旋轉排序”和“稠密排序”算法的漸近最優性，並對“旋轉排序”算法進行了最壞情況分析；第9~10章紹了開放車間極小化完工時間k次方和問題，證明了“最短加工時間分塊”啟發式算法的漸近最優性.

流水車間與開放車間調度算法漸近分析

基本介紹

內容簡介

前言

圖書目錄

相關詞條

熱門詞條