m-n不同順序工件排序算法的研究.pdf

1、生產(chǎn)調(diào)度問題是自動(dòng)化管理領(lǐng)域中一個(gè)十分重要的問題，而m<'*>n不同順序工件排序問題(也稱單件車間調(diào)度問題)是一個(gè)實(shí)際的生產(chǎn)調(diào)度問題。m<'*.n不同順序工件排序算法是當(dāng)前調(diào)度理論的重要研究內(nèi)容之一，此項(xiàng)研究既可以促進(jìn)調(diào)度理論的發(fā)展及其相關(guān)問題的研究，又可以使企業(yè)實(shí)現(xiàn)生產(chǎn)計(jì)劃的動(dòng)態(tài)調(diào)整。 m<'*>n不同順序工件排序問題是一類具有次序約束和資源約束的組合優(yōu)化問題，是一個(gè)典型的NP難題，而非標(biāo)準(zhǔn)m<'*>n不同順序工件排序

2、問題，由于放寬了資源約束的條件，因而具有更大的尋優(yōu)空間，從而增加了問題的難度。理論上已經(jīng)證明要在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)對這一類問題找到全局最優(yōu)解是不可能的。本文通過對m<'*>cn不同順序工件排序問題的深入分析和研究,根據(jù)問題的特點(diǎn)，提出了適用于工程實(shí)際的算法——基于分配率的m<'*>n不同順序工件排序算法和非標(biāo)準(zhǔn)m<'*>n不同順序工件排序算法，它們均可以在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)尋得問題的較優(yōu)解。論文分別從以下幾方面進(jìn)行論述。 首先，

3、論文對調(diào)度問題及其研究現(xiàn)狀進(jìn)行全面綜述，闡述基于分配率的m<'*>n不同順序工件排序算法以及非標(biāo)準(zhǔn)m<'*>n不同順序工件排序算法的優(yōu)越性。 其次，論文給出基于分配率的m<'*>n不同順序工件排序算法以及非標(biāo)準(zhǔn)m<'*>n不同順序工件排序算法的詳細(xì)描述，包括m<,*>n不同順序工件排序問題在數(shù)學(xué)上的描述、目標(biāo)函數(shù)、算法描述和調(diào)度實(shí)例。 最后，論文根據(jù)生產(chǎn)中的實(shí)際情況，提出一類更實(shí)際的調(diào)度問題——相關(guān)工件的加工排序問