具有時(shí)間不確定性的Job Shop問(wèn)題研究.pdf

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

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