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

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

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