帶資源可用性代價的項目調(diào)度啟發(fā)式算法.pdf

1、項目調(diào)度問題廣泛存在于建筑、工業(yè)生產(chǎn)、軟件開發(fā)、云計算等不同行業(yè)，有效調(diào)度是提高項目效率、降低代價的重要手段。
　　本文考慮帶資源可用性代價和截止期約束，最小化資源可用性代價的項目調(diào)度問題。將原問題劃分為拓撲排列和資源決策兩個子問題，提出多起點迭代搜索啟發(fā)式算法MSIS，與傳統(tǒng)先解決資源決策、后求解拓撲排列的RACP求解方法不同，MSIS先解決拓撲排列問題、再解決資源決策問題;由于傳統(tǒng)方法是將原問題轉(zhuǎn)化為一系列SMRCPSP問題，

2、對這些NP-hard問題的迭代求解使得求解效率不高。提出一個迭代搜索框架，構(gòu)建局部搜索的可行鄰域、基于插入的路徑回連等機制，保證每步都產(chǎn)生可行拓撲序列。通過分析現(xiàn)有資源調(diào)節(jié)策略，發(fā)現(xiàn)單純的遞減資源可用量直到不能再減少的調(diào)節(jié)方式，忽略了部分資源可用量的增加可導(dǎo)致其他資源需求量的降低，從而使得項目整體的資源需求降低;本文提出包含資源一致下降和資源波動下降的兩階段資源調(diào)節(jié)啟發(fā)式算法?？紤]截止期約束的性質(zhì)，提出后向資源波峰下降過程，使得活動在項