SBP與JSP非可行解的判定、修正.pdf

1、機(jī)器調(diào)度問題是實際中應(yīng)用最廣泛的運(yùn)籌學(xué)分支之一,研究它,對于在現(xiàn)有資源條件下提高工作效率和經(jīng)濟(jì)效益有重要的現(xiàn)實意義.該文研究的古典的作業(yè)車間調(diào)度問題(JSP)是最著名最困難的機(jī)器調(diào)度問題之一.該文描述了JSP的線性規(guī)劃模型和網(wǎng)絡(luò)圖模型,介紹了一種易于直觀理解的物理模型——插筷子模型,并證明了插筷子模型與JSP的線性規(guī)劃模型和網(wǎng)絡(luò)圖模型的等價性. 對JSP非可行解進(jìn)行了分析,提出了JSP非可行解的一種簡單的判定方法——前沿法.前沿法通過連

2、續(xù)地搜索工件前沿工序集和機(jī)器前沿工序集的公共元素來檢測給定解的可行性. 對SBP的具體流程,特別是單機(jī)問題進(jìn)行了描述,深入分析了單機(jī)問題解決算法對SBP的可解性的影響,給出了單機(jī)問題解決算法滿足SBP可解性的充分必要條件.作為一個特例,我們證明了基于Schrage算法的SBP總是可解的.提出了一個滿足可解性的修正SBP,并證明了相關(guān)的一系列的結(jié)論. 最后提出了一定約束下的JSP非可行解的修正算法,并證明了算法的正確性.該修正算法受啟發(fā)于