改進啟發(fā)式的并行蟻群算法在置換流水線調(diào)度問題上的應用.pdf

1、置換流水線調(diào)度問題（permutation flow—shop scheduling problem，PFSP）是一個著名的組合優(yōu)化問題，也是一個典型的NP難問題，也是生產(chǎn)管理的核心內(nèi)容，隨著生產(chǎn)規(guī)模的擴大，流水線調(diào)度問題的優(yōu)化對提高資源利用率的作用越來越大。因此對其研究具有重要的理論和現(xiàn)實意義。 蟻群算法是由意大利學者M．Dorigo提出的，主要應用于求解組合優(yōu)化問題，該算法首先應用在旅行商（Traveling Salesma

2、n Problem，簡稱TSP）問題并取得較好的效果。啟發(fā)式信息作為蟻群算法中的一個重要因素，從一定程度上影響著算法的效果，一個好的啟發(fā)式信息可以使算法傾向于構建好的解，然而，一個不恰當?shù)膯l(fā)式信息卻可以使算法陷入困境。對于TSP問題，采用城市之間的距離的倒數(shù)作為啟發(fā)式信息，能夠生成高質(zhì)量的解。但是在PFSP問題上，由于工件加工的序列不同，工件之間加工的時間也是變化的，直接采用螞蟻爬行時間的倒數(shù)作為啟發(fā)式信息并不能直接的反映出該問題的實

3、質(zhì)，其結果甚至比完全不采用啟發(fā)式信息的蟻群算法還要差。另外，由于蟻群算法的收斂時間較長，應用于大規(guī)模數(shù)據(jù)時，算法的需要的運行時間更長，嚴重的降低了算法執(zhí)行的效率。 為此，本文在蟻群系統(tǒng)（Ant Colony System，簡稱ACS）算法的基礎上，針對PFSP問題設計了新的啟發(fā)式算法，并對其進行仿真實驗測試。另外，為了改進算法運行的時間，本文針對大規(guī)模數(shù)據(jù)采用了帶有并行策略的ACS算法，按照一定規(guī)律對數(shù)據(jù)進行分組和并行計算，從而