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

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

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