An Evolutionary Algorithm for Optimal Multiple Project Scheduling.pdf

1、隨著現(xiàn)代軟件工程的飛速增長，對(duì)軟件產(chǎn)品的能否具備競(jìng)爭(zhēng)力來說無疑是一種挑戰(zhàn)。與此同時(shí)，如何有效的確定軟件項(xiàng)目的截止日期以及如何控制項(xiàng)目的成本，已成為越來越受重視的研究問題。迄今為止，在實(shí)際應(yīng)用中，很少有方法能支持工程管理人員對(duì)軟件項(xiàng)目高效進(jìn)行管理，比如通過對(duì)項(xiàng)目任務(wù)的仿真和優(yōu)化預(yù)測(cè)合理的項(xiàng)目截止日期。軟件開發(fā)項(xiàng)目依靠仔細(xì)規(guī)劃的時(shí)間表，然而，再詳細(xì)的時(shí)間表也不能免除項(xiàng)目管理員因?yàn)槿祟惞逃械木窒扌运斐傻腻e(cuò)誤判斷。項(xiàng)目管理者必須考慮應(yīng)如何在需

2、求和突發(fā)時(shí)間中做出權(quán)衡才能實(shí)現(xiàn)利益最大化與代價(jià)最小化。
　　本文描述了一個(gè)多目標(biāo)的多項(xiàng)目調(diào)度的解決方案。用來在軟件生命周期中，支持項(xiàng)目經(jīng)理最優(yōu)的安排項(xiàng)目資源，分配項(xiàng)目任務(wù)，滿足項(xiàng)目需求。軟件項(xiàng)目生
　　命周期中存在三個(gè)優(yōu)化目標(biāo)。這三個(gè)目標(biāo)分別是：
　　第一，通過減少生產(chǎn)的缺陷最大化軟件產(chǎn)品的質(zhì)量。在我們的模型中，我們認(rèn)為，導(dǎo)致更高的軟件開發(fā)時(shí)間和維修費(fèi)用的軟件項(xiàng)目的生產(chǎn)的缺陷需要由開發(fā)人員通過返修來解決。提高產(chǎn)品質(zhì)量的

3、影響被認(rèn)為與不同方面的項(xiàng)目成果相關(guān)。
　　第二，為了評(píng)價(jià)項(xiàng)目完工時(shí)間，一份完善的軟件開發(fā)進(jìn)度時(shí)間表是必備的。對(duì)于項(xiàng)目中的每個(gè)模塊，每項(xiàng)活動(dòng)的具體時(shí)間被計(jì)算并且各模塊的最長時(shí)間決定了項(xiàng)目完工時(shí)間。
　　第三，最小化工程造價(jià)。工程造價(jià)應(yīng)該正比于為每個(gè)任務(wù)付出的努力，可以用每個(gè)活動(dòng)所需的總時(shí)間乘以單位時(shí)間的成本來測(cè)量。軟件項(xiàng)目成本決定了該軟件在軟件市場(chǎng)中的成功率和競(jìng)爭(zhēng)力。
　　項(xiàng)目時(shí)間表的主要目的是給出合適的“脈絡(luò)圖”，以便

4、協(xié)助項(xiàng)目管理者有效地完成該項(xiàng)目。項(xiàng)目管理者制定的時(shí)間表用來反映該項(xiàng)目要如何實(shí)現(xiàn)以及正確反應(yīng)項(xiàng)目開發(fā)過程中的變化。項(xiàng)目進(jìn)度計(jì)劃闡明了要做的任務(wù)和活動(dòng)，誰將承擔(dān)這些任務(wù)（資源），什么時(shí)間應(yīng)該完成（項(xiàng)目時(shí)間）。在實(shí)際項(xiàng)目開發(fā)過程中，項(xiàng)目進(jìn)度時(shí)間表被用來監(jiān)管項(xiàng)目進(jìn)度，指定項(xiàng)目何時(shí)開始，何時(shí)完成該項(xiàng)目，以及如何合理的進(jìn)行資源分配。
　　近年來，為提高對(duì)軟件項(xiàng)目過程的認(rèn)識(shí)和調(diào)度，建立了最優(yōu)化模型。使用優(yōu)化模型進(jìn)行項(xiàng)目管理引入的一個(gè)具有挑戰(zhàn)性的

5、問題是如何支持項(xiàng)目管理者最好地安排項(xiàng)目資源和任務(wù)，以滿足項(xiàng)目約束條件和要求。
　　我們旨在為每個(gè)項(xiàng)目任務(wù)設(shè)計(jì)最有效的開發(fā)方案，在增加產(chǎn)品質(zhì)量的同時(shí)能夠減少項(xiàng)目工期和成本。我們?cè)O(shè)計(jì)的模型包括編碼、檢查、測(cè)試、返修操作等幾個(gè)階段，同時(shí)也包括將項(xiàng)目任務(wù)分配給開發(fā)者生成項(xiàng)目進(jìn)度表。
　　一般情況下，一個(gè)給定的軟件項(xiàng)目的時(shí)間安排是一個(gè)由項(xiàng)目管理者手動(dòng)建立的任務(wù)。制定項(xiàng)目進(jìn)度計(jì)劃需要耗費(fèi)大量的時(shí)間、精力，并且還需要具備關(guān)于可用資源的知識(shí)

6、以及項(xiàng)目進(jìn)度安排的經(jīng)驗(yàn)。然而，這項(xiàng)任務(wù)并沒有完全擺脫由于管理者的局限性做出的錯(cuò)誤決策，如缺乏對(duì)組織目標(biāo)和資源的知識(shí)，基于不正確的假設(shè)的決策等等。一個(gè)完善的項(xiàng)目日程可以用于預(yù)測(cè)何時(shí)能完成項(xiàng)目活動(dòng)。此外，它允許項(xiàng)目管理者查看項(xiàng)目的性能，并使用這些數(shù)據(jù)更精確地展望預(yù)期的工作。然而，建立一個(gè)準(zhǔn)確和可實(shí)現(xiàn)的項(xiàng)目時(shí)間表是開發(fā)一個(gè)項(xiàng)目的關(guān)鍵活動(dòng)之一。同樣，定期更新和維護(hù)項(xiàng)目進(jìn)度，以此來跟蹤正在執(zhí)行的項(xiàng)目進(jìn)度也是非常重要的?？紤]到人工開發(fā)調(diào)度的必要性以

7、及它存在的缺陷，找到另一種方法在設(shè)計(jì)項(xiàng)目進(jìn)度的早期階段用以協(xié)助管理人員是十分有價(jià)值的。
　　在此前提下，我們提出了一種制定軟件項(xiàng)目中的超時(shí)計(jì)劃。因?yàn)樵谲浖こ讨须y免會(huì)出現(xiàn)超時(shí)的現(xiàn)象，這會(huì)影響到開發(fā)者，甚至?xí)?dǎo)致軟件成本和軟件缺陷增加。對(duì)此，我們?cè)u(píng)估了額外的開銷和超時(shí)時(shí)間。為了解決這一問題，我們采用多目標(biāo)遺傳算法，對(duì)項(xiàng)目質(zhì)量、成本、工期和開發(fā)技能，以目標(biāo)函數(shù)的形式，優(yōu)化各個(gè)方面調(diào)度和人事安置。MOEA/D-DE我們的工作中被使用，它

8、對(duì)復(fù)雜帕累托形狀集合的多目標(biāo)優(yōu)化問題表現(xiàn)良好。我們改進(jìn) MOEA/D-DE算法用以開發(fā)軟件項(xiàng)目時(shí)間表。算法包括遺傳算法的標(biāo)準(zhǔn)程序，它包含：創(chuàng)建初始種群、表示不同的人口的個(gè)體、選擇適者生存的個(gè)體、應(yīng)用個(gè)體配偶的交叉操作和在產(chǎn)生孩子中應(yīng)用變異算子。
　　那么，我們?nèi)绾芜M(jìn)行一系列的計(jì)算實(shí)驗(yàn)來評(píng)價(jià)多目標(biāo)模型和分解的啟發(fā)式算法呢？如何呈現(xiàn)我們是如何實(shí)施和執(zhí)行優(yōu)化模型和算法呢？為了回答這些問題，我們確定了單一的仿真運(yùn)行的平均運(yùn)行的時(shí)間和總的運(yùn)

9、行的時(shí)間。
　　在本論文中實(shí)現(xiàn)對(duì)多個(gè)軟件項(xiàng)目進(jìn)行調(diào)度的問題，該方法旨在軟件項(xiàng)目調(diào)度的早期階段協(xié)助項(xiàng)目管理者進(jìn)行軟件開發(fā)的時(shí)間表的指定。我們把調(diào)度多個(gè)軟件項(xiàng)目的問題當(dāng)作多目標(biāo)問題，實(shí)現(xiàn)對(duì)軟件項(xiàng)目的最佳調(diào)度，以達(dá)到提高產(chǎn)品質(zhì)量的目的。同時(shí)也盡量減少項(xiàng)目完工時(shí)間和成本。這項(xiàng)研究將評(píng)估軟件項(xiàng)目中的調(diào)度過程。
　　我們?cè)O(shè)計(jì)兩種不同類型的實(shí)驗(yàn)進(jìn)行分析。實(shí)驗(yàn)?zāi)康陌ㄈ齻€(gè)方面：第一，探討多目標(biāo)模型和提出的MOEA/D-DE算法在解決多項(xiàng)目調(diào)

10、度問題的效率；第二，研究不同開發(fā)人員在設(shè)計(jì)的項(xiàng)目時(shí)間表方面的技能；第三，通過加班，說明軟件項(xiàng)目成本和項(xiàng)目完工時(shí)間之間可能的權(quán)衡。
　　描述如何評(píng)價(jià)多目標(biāo)模型和算法。此外，我們對(duì)得到的結(jié)果進(jìn)行審查和分析。相信本文的研究成果為軟件項(xiàng)目的開發(fā)添加了一個(gè)有效的工具。最后，提出對(duì)后續(xù)研究問題展望和本文涉及的幾個(gè)問題的擴(kuò)展與延伸。
　　在所提出的問題中，考慮到優(yōu)化目標(biāo)，將最高效的人力資源集合分配給每個(gè)項(xiàng)目活動(dòng)，目的是為了最小化目標(biāo)函數(shù)。