具有相同設備的Job Shop調(diào)度問題的研究.pdf

1、車間作業(yè)調(diào)度問題(JSSP)是一類具有時間約束、次序約束和資源約束的組合優(yōu)化問題。理論上已經(jīng)證明，JSSP是NP難問題，沒有一個有效的算法能在多項式時間內(nèi)求出其最優(yōu)解。本文所研究的具有相同設備的車間作業(yè)調(diào)度問題是指能夠加工同一道工序的設備不唯一，即存在一設備子集，其中的任意一臺設備都能加工該道工序。顯然，此類調(diào)度問題放寬了資源(設備)約束條件，擴大了尋優(yōu)空間，增加了問題的難度。 本文的研究目標是在滿足約束條件的情況下，如何找到一

2、種合適的排序，確定每道工序的開始加工時間，使得總的加工時間盡可能小。首先對具有相同設備的單產(chǎn)品Job Shop調(diào)度問題進行建模，將單產(chǎn)品映射為加工樹；然后，確定所構造加工樹的關鍵路徑，并將關鍵路徑上的工序入棧，對棧中工序進行遍歷尋找叉點工序，并依據(jù)所找到的叉點工序?qū)庸溥M行分段，根據(jù)段內(nèi)工序的特點將工序分為相關工序和獨立工序，并采用前沿貪心規(guī)則和最優(yōu)適應規(guī)則對段內(nèi)工序制定相應的目標函數(shù)；最后根據(jù)段內(nèi)工序的特點和相同設備資源之間的互補性

3、對不同類型的工序采用不同的優(yōu)化策略。同時，提出了一種以根對齊的方式將多產(chǎn)品或動態(tài)加入的產(chǎn)品構造成虛擬加工樹的方法，從而對多產(chǎn)品或動態(tài)產(chǎn)品調(diào)度問題進行簡化。對于動態(tài)JobShop調(diào)度問題，當動態(tài)產(chǎn)品到達時，應對初始時刻到達的產(chǎn)品工序進行判斷，以確定初始時刻產(chǎn)品的剩余工序，然后將初始時刻產(chǎn)品的剩余工序構造成一棵加工樹，并將其與動態(tài)到達的產(chǎn)品構造成一棵新的虛擬加工樹，將用來存放初始時刻產(chǎn)品工序的棧和隊列清空，重新確定所構造的新虛擬加工樹的關鍵