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

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

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