[發(fā)明專利]基于多目標優(yōu)化的主動?反應式動態(tài)項目調度方法

有效

• 申請?zhí)枺?/td>: 201410307479.3
• 申請日: 2014-06-30
• 公開（公告）號: CN104077634B
• 公開（公告）日: 2017-02-08
• 發(fā)明（設計）人: 申曉寧;李愛民;張敏
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 南京匯盛專利商標事務所(普通合伙)32238
• 代理人: 張立榮

1.一種基于進化多目標優(yōu)化的主動-反應式動態(tài)項目調度方法，包括如下步驟：

(1)初始化：讀取項目初始時的輸入信息，包括每個任務的工作量、技能要求、任務優(yōu)先級圖，每位軟件工程師所掌握的技能、可在本項目中投入的最大工作量、正常月薪、加班月薪；給出優(yōu)化目標的定義；將項目初始時刻視為初始調度點t₀，將緊急動態(tài)事件的發(fā)生時刻視為重調度點t_l(l＝1,2,…)；在t_l(l＝0,1,2,…)時刻所處的項目開發(fā)環(huán)境下，項目工期和成本分別定義為完成當前所有任務剩余的工作量所花費的時間開銷和財力；本發(fā)明通過對不確定因素進行多次仿真，以比較項目成本或工期的實際值與預估值之間的差值，并將此定義為抗風險能力；穩(wěn)定性僅在t_l(l＝1,2,…)有定義，本發(fā)明將其定義為軟件工程師在新舊方案各個任務中投入的工作量的差別；所設定的約束條件包括任務技能約束，以及軟件工程師不能超負荷工作的約束；

(2)在項目初始時刻t₀，采用主動調度方式生成一個預測方案；根據(jù)項目初始時刻任務和軟件工程師的屬性，基于靜態(tài)多目標進化算法，同時優(yōu)化項目的以下目標：項目成本、工期以及抗風險能力，預先產(chǎn)生一組在多個目標間進行折中的調度方案，供項目管理者進行參考，并從中挑選出一個滿意解；

(3)在項目開發(fā)過程的每個重調度點t_l(l＝1,2,…)時刻，采用由緊急事件驅動的基于動態(tài)多目標進化算法的反應式重調度方式；依據(jù)任務和軟件工程師的當前屬性，通過捕捉項目中不同類型緊急動態(tài)事件(軟件工程師請假離開、軟件工程師回歸、新的緊急任務下達)的特征，并充分利用已有的歷史調度方案信息，在多目標進化算法的群體初始化中引入與問題知識相關的啟發(fā)式動態(tài)優(yōu)化策略，使得算法快速地適應動態(tài)變化的環(huán)境，在較短的時間內產(chǎn)生一組在項目的成本、工期、抗風險能力及穩(wěn)定性之間折中的新的調度方案，并由項目管理者從中挑選出一個滿意解；該方案在項目中一直執(zhí)行，直到下一個緊急事件發(fā)生，重新啟動動態(tài)多目標進化算法進行調度。

2.根據(jù)權利要求1所述的調度方法，其中步驟(1)所述的t_l(l＝0,1,2,…)時刻的項目工期定義為：

f1(tl)=durationI=max{j|Tj∈_ava_set(tl)}(Tjend(tl))-min{j|Tj∈T_ava_set(tl)}(Tjstart(tl))]]>

其中，和分別表示在t_l時刻的調度方案中，任務T_j的開始時間和完成時間；T_ava_set(t_l)表示t_l時刻所有可進行調度的任務的集合；I表示初始景象，它將對不確定屬性的估計值作為該屬性的值計算項目工期；

步驟(1)所述的t_l(l＝0,1,2,…)時刻的項目成本定義為：

f2(tl)=costI=Σt′≥tlΣei∈e_ava_set(tl)e_costit′]]>

e_costit′=einorm_salary·t′·Σj∈T_active_set(t′)xij(tl)Σj∈T_active_set(t′)xij(tl)≤1einorm_salary·t′·1+eiover_salary·t′·(Σj∈T_active_set(t′)xij(tl)-1)1<Σj∈T_active_set(t′)xij(tl)≤eimaxded]]>

其中，t'表示項目處于開發(fā)階段的某一個月，表示在t'期間付給軟件工程師e_i的薪酬；T_active_set(t')表示在t'期間正在進行開發(fā)的任務集合；x_ij(t_l)表示在t_l時刻的重調度方案中，e_i在任務T_j中投入的工作量占全日制工作量的百分比；表示e_i能夠對整個項目投入的最大工作量占全日制工作量的百分比，表示e_i能夠加班工作；和分別表示e_i的正常和加班月薪；e_ava_set(t_l)表示在t_l時刻所有參與該項目的軟件工程師的集合；

步驟(1)所述的t_l(l＝0,1,2,…)時刻調度方案的抗風險能力定義為：

f3(tl)=robustness=1NΣq=1N(max(0,durationq(tl)-durationI(tl)durationI(tl)))2+λ1NΣq=1N(max(0,costq(tl)-costI(tl)costI(tl)))2]]>

抗風險能力采用基于景象的方法定義，將一個調度方案在不確定屬性的多種采樣值{θ_q|q＝1,2,…,N}下進行仿真，以比較項目成本或工期的實際值與預估值之間的差值；其中，θ_q是不確定屬性的第q個采樣值，N是樣本個數(shù)(在本發(fā)明中，設置N＝30)；duration_q和cost_q分別是采樣值θ_q下相應的項目工期和成本目標值；λ為權系數(shù)，在本發(fā)明中，令λ＝1；

步驟(1)所述的t_l(l＝1,2,…)時刻的穩(wěn)定性定義為：

f4(tl)=stability=Σ{i|ei∈e_ava_set(tl-1)∩e_ava_set(tl)}Σ{j|Tj∈T_ava_set(tl-1)∩T_ava_set(tl)}ωij|xij(tl)-xij(tl-1)|]]>

穩(wěn)定性的公式只針對在t_l和t_l-1時刻均需調度的任務進行計算，權值ω_ij設置如下：

ωij=2ifxij(tl-1)=0andxij(tl)>01.5ifxij(tl-1)>0andxij(tl)=01else]]>

如果在t_l-1時刻的方案中，軟件工程師e_i未被分配到任務T_j中，而在t_l時刻的新方案中，安排e_i去做T_j，則施加一個較大的懲罰因子ω_ij＝2；如果在原方案中，e_i被分配到任務T_j中，但在新方案中，未安排e_i參加T_j，則施加一個中等的懲罰因子ω_ij＝1.5；如果新舊方案都安排e_i參加T_j，但工作量的投入不同，則施加一個小的懲罰因子ω_ij＝1；

步驟(1)所述的任務技能約束指參與某項任務的所有軟件工程師必須具備該任務要求的所有技能，即

∀Tj∈T_ava_set(t;),s.t.reqj⊆∪ei∈e_ava_set(tl){skilli|xij(tt)>0}]]>

其中，req_j表示任務T_j所需求的技能的集合，skill_i表示軟件工程師e_i所掌握的所有技能的集合；

步驟(1)所述的軟件工程師不能超負荷工作的約束指在任一時期t'≥t_l，一個軟件工程師為正在進行開發(fā)的任務同時投入的工作量之和不超過他對整個項目投入的最大允許工作量，即，

∀ei∈e_ava_set(tl),∀t′≥tl,s.t.e_workit′=Σj∈T_active_set(t′)xij(tl),]]>且e_workit′≤eimaxded]]>