基于剩余函數(shù)的Job-Shop調(diào)度算法的研究.pdf

1、生產(chǎn)調(diào)度問題是自動(dòng)化管理領(lǐng)域中一個(gè)十分重要的問題,而單件車間(Job-Shop)調(diào)度問題是一個(gè)實(shí)際的生產(chǎn)調(diào)度問題。單件車間調(diào)度算法是當(dāng)前調(diào)度理論的重要研究?jī)?nèi)容之一,此項(xiàng)研究既可以促進(jìn)調(diào)度理論的發(fā)展及其相關(guān)問題的研究,又可以使企業(yè)實(shí)現(xiàn)生產(chǎn)計(jì)劃的動(dòng)態(tài)調(diào)整。Job-Shop調(diào)度問題是一類具有次序約束和資源約束的組合優(yōu)化問題,是一個(gè)典型的NP難題,而非標(biāo)準(zhǔn)Job-Shop調(diào)度問題,由于放寬了資源約束的條件,因而具有更大的尋優(yōu)空間,從而增加了問題

2、的難度。理論上已經(jīng)證明要在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)對(duì)這一類問題找到全局最優(yōu)解是不可能的。本文通過對(duì)Job-Shop調(diào)度問題和非標(biāo)準(zhǔn)Job-Shop調(diào)度問題的深入分析和研究,根據(jù)問題的特點(diǎn),提出了兩種適用于工程實(shí)際的算法——基于剩余函數(shù)的Job-Shop調(diào)度算法和非標(biāo)準(zhǔn)Job-Shop調(diào)度的效率算法,它們均可以在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)尋得較優(yōu)解。論文分別從以下幾方面進(jìn)行論述。首先,論文對(duì)調(diào)度問題及其研究現(xiàn)狀進(jìn)行全面綜述,闡述基于剩余函數(shù)的Job-S