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

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

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

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