改進(jìn)的D時(shí)刻表求解時(shí)間規(guī)劃問(wèn)題.pdf

1、本文對(duì)時(shí)間規(guī)劃中D_時(shí)刻表進(jìn)行深入的探討,使用時(shí)間規(guī)劃運(yùn)算中較為普遍的時(shí)間矩陣模型,給出D_時(shí)刻表算法的詳細(xì)步驟,并針對(duì)D_時(shí)刻表算法的不足,提出改進(jìn)完善的意見(jiàn)。最后設(shè)計(jì)一個(gè)時(shí)間規(guī)劃系統(tǒng),從而我們更深層次理解時(shí)間規(guī)劃的原理和機(jī)制。
　　D_時(shí)刻表是時(shí)間規(guī)劃算法中較為先進(jìn)的一種,它可以在若干存在關(guān)系約束和寬度約束的時(shí)間區(qū)間中找到同時(shí)滿足兩種約束的規(guī)劃方案。但在其實(shí)際應(yīng)用中,我們發(fā)現(xiàn)它的一些局限性和不完善的地方,如:
　　(a)

2、算法中輸入的矩陣是化簡(jiǎn)后的矩陣,它的行列數(shù)目不一定是偶數(shù);而且行列與原時(shí)間區(qū)間端點(diǎn)的對(duì)應(yīng)關(guān)系也不再一一對(duì)應(yīng)。
　　(b)算法中沒(méi)考慮區(qū)間關(guān)系約束的一些附加約束條件,而這些條件在實(shí)際應(yīng)用中往往是不能忽略的。
　　(c)算法中時(shí)間點(diǎn)的賦值由關(guān)系約束和寬度約束決定,而實(shí)際應(yīng)用中某些特殊時(shí)間點(diǎn)的賦值需要我們特別指定。
　　(d)算法中單成分的時(shí)間規(guī)劃問(wèn)題都已解決,針對(duì)多成分關(guān)系的情況,算法難以解決。
　　(e) D_時(shí)刻

3、表算法雖然優(yōu)良,但是在實(shí)例中所表現(xiàn)出來(lái)算法時(shí)間復(fù)雜度依然比較高。
　　在實(shí)際工作中,我們不斷的對(duì)其改進(jìn)和完善,加入了一些新的特性、運(yùn)算和處理,使算法更適應(yīng)于真實(shí)的環(huán)境。
　　(a)在矩陣化簡(jiǎn)中加入合并鏈,記錄和查找簡(jiǎn)化時(shí)間矩陣和原時(shí)間關(guān)系矩陣的行列對(duì)應(yīng)關(guān)系。
　　(b)加入空事件,調(diào)整時(shí)間區(qū)間的滯后值。
　　(c)加入重定位算法,調(diào)整特殊時(shí)間點(diǎn)的賦值。
　　(d)使用遺傳算法來(lái)求解多成份時(shí)間關(guān)系下D_時(shí)刻表