具有時間不確定性的Job Shop問題研究.pdf

1、 機器調(diào)度問題來源于不同的領域，如柔性制造系統(tǒng)、生產(chǎn)計劃、計算機設計、后勤及通信等，這些問題的共同特性是沒有一個有效的算法能在多項式時間內(nèi)求出最優(yōu)解。古典的作業(yè)車間問題(JobShopProblem，JSP)是最著名的機器調(diào)度問題之一。在過去的40年里，機器調(diào)度問題吸引了無數(shù)研究者的濃厚興趣，大量的研究成果相繼問世，但是對于調(diào)度問題的研究一般都在于靜態(tài)調(diào)度問題的研究。可是在實際世界中調(diào)度很少是靜態(tài)的，在調(diào)度執(zhí)行過程中一些事件的發(fā)生

2、往往是不可預測的，而一些事件的不可預測往往引起的是時間的不確定。 本文研究了具有時間不確定性的的作業(yè)車間問題，以古典的作業(yè)車間問題為背景，加入處理時間不確定性因素——處理時間在一個閉區(qū)間的范圍內(nèi)變化。為了求解含有該類不確定性時間因素的作業(yè)車間問題，我們以確定性車間調(diào)度問題的求解為基礎，對一個確定性的作業(yè)車間問題進行分離邏輯(DifferenceLogic)建模，使用分離邏輯求解器求出一個近似最優(yōu)的調(diào)度結果，在調(diào)度執(zhí)行過程中使用插