一種多項目調(diào)度的改進(jìn)蟻群算法研究

張勇明　陳曄　吳志飛

【摘 要】提出一種用于資源約束下多項目調(diào)度問題的改進(jìn)蟻群算法，該算法基于最大最小螞蟻基礎(chǔ)算法，在解的構(gòu)建過程中使用偽隨機(jī)比例行為選擇規(guī)則，并在每一次迭代中應(yīng)用禁忌搜索算法進(jìn)行局部優(yōu)化。最后仿真實(shí)例表明該算法在多項目調(diào)度中有良好的優(yōu)化性能。

【關(guān)鍵詞】多項目調(diào)度；蟻群算法；禁忌搜索

資源約束下多項目調(diào)度問題RCMPSP（Resource-Constrained Multi-Project Scheduling Problems）是一類重要調(diào)度問題，優(yōu)化目標(biāo)是有資源競爭時的多個項目的總工期最短。目前主要求解算法包括兩類：基于規(guī)則的啟發(fā)式算法[1]和智能優(yōu)化算法[2]。本文針對該問題，提出一種改進(jìn)的蟻群算法[3]，以最大最小螞蟻算法[4]為基礎(chǔ)，選擇最早可行起始時間作為螞蟻搜索的啟發(fā)式指導(dǎo)信息，同時對每次迭代結(jié)果引入禁忌搜索算法進(jìn)一步優(yōu)化。

1 RCMPSP問題蟻群算法描述

為解決蟻群算法在多項目調(diào)度問題中易陷入局部最優(yōu)的問題，本文對最大最小螞蟻算法MMAS進(jìn)行了改進(jìn)，在解的構(gòu)建過程中使用偽隨機(jī)比例行為選擇規(guī)則，并采用積極的行為選擇規(guī)則以加快算法收斂速度。在引入的禁忌搜索中采用2-opt交換局部搜索，幫助算法跳出可能的局部最優(yōu)，同時通過將存在未完成緊前任務(wù)的任務(wù)和等待資源的任務(wù)加入禁忌表，能降低算法運(yùn)算時間。本文提出的改進(jìn)蟻群算具體迭代步驟如下：

step1： 數(shù)據(jù)初始化，包括讀入問題實(shí)例的網(wǎng)絡(luò)圖，初始化信息素矩陣和啟發(fā)式信息矩陣，初始化信息素的上界與下界，初始化螞蟻的記憶；……