含有維護的單機與平行機調(diào)度問題研究.pdf

1、調(diào)度問題是一類資源優(yōu)化配置問題，它廣泛應用于工程、計算機和管理等諸多領(lǐng)域，尤其在制造業(yè)和服務業(yè)中扮演著重要的角色。在當前的競爭環(huán)境中，科學合理的調(diào)度不僅可以幫助企業(yè)充分利用已有的資源，還可以提高企業(yè)的生產(chǎn)率，進而為企業(yè)在市場競爭中占有有利地位提供強有力的技術(shù)支持。
　　近年來，對調(diào)度問題的研究越來越多，新模型也不斷涌現(xiàn)。其中含有維護的調(diào)度問題已成為調(diào)度領(lǐng)域里的一個研究熱點。本文主要研究了兩個含有維護的調(diào)度問題。
　　第一個問

2、題是維護時長依賴于機器負載和機器空閑的單機調(diào)度問題。我們考慮了一個含有單次維護的單機調(diào)度問題，其中工件不可中斷，維護的開始時刻給定但維護時長是維護之前機器負載和機器空閑時長的線性增函數(shù)，目標是最小化時間表長。我們分三種情況進行討論，對前兩種情況分別給出了一個多項式時間最優(yōu)算法，對最后一種情況分析了經(jīng)典的LPT算法的性能并給出了通過經(jīng)典背包問題的任意一個FPTAS來獲得該情況的一個FPTAS的方法。
　　第二個問題是含有特殊工件和機