柔性Flow shop啟發(fā)式調(diào)度算法的漸近最優(yōu)分析.pdf

1、調(diào)度問題在柔性制造系統(tǒng)、現(xiàn)代物流、計算機科學等領域中非常重要，但絕大多數(shù)調(diào)度問題是NP-hard問題，幾乎不可能有多項式時間復雜度的最優(yōu)求解算法，大量研究工作主要集中在近似算法的設計和分析。而調(diào)度問題的規(guī)模一般較大，分析其近似算法的絕對性能比往往很困難，有時甚至不可行。因此，研究近似算法的漸近性能比就顯得很有必要。 對于目標函數(shù)為作業(yè)加權完成時間和的單機、平行機、flowshop、jobshop調(diào)度問題，可以基于加權最短處理時間

2、的啟發(fā)式算法獲得漸近最優(yōu)解。本論文的目的就是研究這種漸近最優(yōu)的簡單經(jīng)驗規(guī)則是否也適合更復雜的調(diào)度問題。首先，本論文研究了同速處理機中心的柔性Flowshop加權完成時間調(diào)度問題。針對該問題的每個子問題，本文研究了兩個基于瓶頸處理機中心的(有效作業(yè))加權最短處理時間的啟發(fā)式算法，并使用機器模型分組和概率分析方法，證明了它們是漸近最優(yōu)的。 其次，本論文研究了恒速處理機中心的柔性Flowshop加權完成時間調(diào)度問題。針對該問題的每個子