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

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

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