结合模拟与基因演算法

1、Southern Taiwan University Graduate Program of Industrial Management結合模擬與基因演算法結合模擬與基因演算法求解軟體開發之多專案排程問題求解軟體開發之多專案排程問題Using Simulation and Genetic Algorithm to Solve The Scheduling Problem of Multiple Software Development Projects研研 究究 生：黃逸帆生：黃逸帆指導教授：葉榮懋指導教授：葉榮懋中華民國一百年三月中華民國一百年三月Southern Taiwan Univer

2、sity Graduate Program of Industrial Management南台科技大學南台科技大學工業管理研究所工業管理研究所Southern Taiwan University Graduate Program of Industrial Management2報告大綱報告大綱緒論文獻探討研究方法案例驗證未來研究方向與預期成果Southern Taiwan University Graduate Program of Industrial Management3緒緒 論論研究動機研究目的研究架構緒論緒論文獻探討文獻探討案例驗證案例驗證研究方法研究方法預期成果預期成果Sout

3、hern Taiwan University Graduate Program of Industrial Management4研究動機研究動機(1/2)因應全球資訊化的來臨以及全球性市場的競爭與大環境變動，不論是政府機關、企業組織或個人單位針對軟體開發專案排程的需求也日益增加。如何對資源做出有效的管理以及對專案排程方面做出有效的規劃便成為各個企業最首要的努力方向與目標 。Southern Taiwan University Graduate Program of Industrial Management5研究動機研究動機(2/2)妥善的資源分配與恰當的專案排程不但可使企業本身的獲利有所提

4、升，更能加強企業自身的競爭力，還能創造出企業本身與其他競爭者有所區別的價值，因此專案排程與其資源分配是極具探討的價值存在。 Southern Taiwan University Graduate Program of Industrial Management6研究目的研究目的以系統模擬解決軟體開發的多專案排程問題，並以試算表建構多專案管理的模擬模式，並對其進行求解。利用基因演算法求解多專案排程的人力資源配置問題，藉此達到在完工期限內完成與降低成本的目標，最後將其結果提供決策者做參考之依據 。Southern Taiwan University Graduate Program of Indu

5、strial Management7研究架構研究架構決定研究方向文獻回顧專案管理專案排程系統模擬基因演算建立研究架構執行模擬與基因演算的實例驗證分析結果結論與建議Southern Taiwan University Graduate Program of Industrial Management8文獻探討文獻探討專案管理排程策略系統模擬基因演算法緒論緒論文獻探討文獻探討案例驗證案例驗證研究方法研究方法預期成果預期成果Southern Taiwan University Graduate Program of Industrial Management9專案的定義及特性專案的定義及特性Newm

6、an et al（1987）對專案的定義及描述為：組織資源的整合，以創造前所未有的某項事務，而該項事務將在組織策略的設計與建制上提供性能的能力，專案有明顯的生命週期，它開始於一個想法，透過設計、工程、製造或建構，並經由專案所有的人使用而產生。 Kerzner（1990）將專案定義為：有一定的開始日期及完成日期，並運用特定的經費與資源來完成明確目標的工作。 Southern Taiwan University Graduate Program of Industrial Management10專案管理專案管理Cleland & King （1983）將專案管理界定為應用系統途徑以從事技

7、術複雜而以時間、成本、績效明顯定義目標的工作。 Lewis（1998）專案管理是一種具有效率及效益的將專案成功執行的一種程序與方法；而其所關切的是如何將一項任務能如期、如質及預算內達成並充分滿足需求目標。 Southern Taiwan University Graduate Program of Industrial Management11專案排程專案排程為了要決解排程問題，許多學者提出各種排程理論及方法，主要可分為以下幾種：l常用派工法（Dispatching Rule）l學規劃法（Mathematical Programming）l啟發法（Heuristic Rule）l基因演算法（G

8、enetic Algorithm）l電腦模擬法（Simulation）l人工智慧（Artificial Intelligence）Southern Taiwan University Graduate Program of Industrial Management12派工法則派工法則(1/2)Putnum et al（1971）、Holthaus & Rajendran（1997），Petroni & Rizzi（2002），皆有關於優先派工法則之詳盡研究，其中提及了最短加工時間法、先到先服務法、後到先服務法與加權最短加工時間法等。 Southern Taiwan Unive

9、rsity Graduate Program of Industrial Management13派工法則派工法則(2/2)派工法則派工法則定義定義型式型式最短加工時間最短加工時間（Shortest Processing Time, SPT ）作業花在工作站時間越短越優先；最作業花在工作站時間越短越優先；最迫切、緊急的作業優先。迫切、緊急的作業優先。靜態靜態最早到期日最早到期日（Earliest Due Date, EDD）作業顧客到期日愈近者優先。作業顧客到期日愈近者優先。靜態靜態顧客關係顧客關係（PCO）關係較佳的顧客先處理，似最高優關係較佳的顧客先處理，似最高優先順序，即作業優先順序最高

10、先順序，即作業優先順序最高先處理。先處理。靜態靜態加權最短加工時間法加權最短加工時間法（Weight Shortest Process Time, WSPT）工作在機台中之加工時間與其權重之工作在機台中之加工時間與其權重之比率，比率最小的優先加工。比率，比率最小的優先加工。靜態靜態先到先服務先到先服務（First in First Service, FIFS）最先到達的作業最先處理，略優於隨最先到達的作業最先處理，略優於隨機方式。機方式。靜態靜態後到先服務後到先服務（Last in First Service, LIFS）最後到達的作業最先處理，此法似最後到達的作業最先處理，此法似最早到期日法

11、。最早到期日法。靜態靜態最小寬裕時間法最小寬裕時間法（Minimum Slack Time, MST）工作之寬裕時間與加工時間之差距，工作之寬裕時間與加工時間之差距，差距最小者優先加工。差距最小者優先加工。動態動態寬裕時間寬裕時間/所剩未完成作業所剩未完成作業（Slack Time /Remaining Operations）寬裕時間除以所剩未完成之作業目，寬裕時間除以所剩未完成之作業目，比率最小優先處理。比率最小優先處理。動態動態關鍵比率關鍵比率（Critical Ratio, CR）工作之寬裕時間對加工時間的比率，工作之寬裕時間對加工時間的比率，比率愈小的先處理。比率愈小的先處理。動態動態

12、在製品在製品（Work In Process, WIP）在製品最多者優先處理。在製品最多者優先處理。動態動態隨機選擇隨機選擇（R&om Selection, RS）隨機選擇選中的先處理。隨機選擇選中的先處理。動態動態混合式混合式（Combination）應用個以上的派工法則。應用個以上的派工法則。動態動態Southern Taiwan University Graduate Program of Industrial Management14系統模擬（系統模擬（1/2）Law & Kelton （2000）等學者認為系統是對設備及其運作程序的研究，通常會設定一連串的假設與限制以

13、規範其運作。這些假設通常會以學式與邏輯關係陳述，組成模型，而此模型即可用於瞭解系統的行為。模型的邏輯關係簡單的話，則可以用學模式求解。然而真實系統通常相當複雜，學模式不容易分析，故常會選擇使用模擬的方式解決。 Southern Taiwan University Graduate Program of Industrial Management15系統模擬（系統模擬（2/2）Harrell et al（1992）認為是模擬是一個以擬真系統進行實驗的方法，來確定系統對於本體結構、環境或假設的改變會如何反應。建立一個似真實系統之邏輯模式，透過運作方式，瞭解系統運作之行為，根據各種系統決策參，提供管

14、理者決策參，作為改善系統績效。Southern Taiwan University Graduate Program of Industrial Management16系統模擬的優缺點（系統模擬的優缺點（1/2）Law Kelton（2000）所提出電腦模擬的優點如下：l當問題太過於複雜、混亂時，建構出的學模型會過於龐大以及計算時間過長，此時模擬便是適合應用的研究工具。 l當需要對一個系統作各種不同參變化的實驗時，利用模擬的方法可以很方便又快速的完成結果，比直接在實體系統上實驗容易控制實驗的各個變因。 l碰到一個需要長時間研究的系統時，利用模擬可以壓縮觀察的時間，也可以用來預估長時間以後的系

15、統狀況。 Southern Taiwan University Graduate Program of Industrial Management17系統模擬的優缺點（系統模擬的優缺點（2/2）Law Kelton（2000）所提出電腦模擬的缺點如下：l單一模擬方法只能依照給定的參對系統做出評估值，並不能達到最佳化的效果。 l構建一個完整的模擬模型是非常費時。l若是在模擬過程中，模式不能很完全地代表實體的系統，則模擬產生出來的系統績效值將會誤導使用者，並且模擬的結果只能反映出實體系統的部份資訊而已。 Southern Taiwan University Graduate Program of

16、Industrial Management18模擬方法模擬方法目前有三種型電腦程式語言可進行模擬。l一般目的型的模擬語言，包含Visual Basic 、C+及Java。 l特殊目的型的模擬語言，包含GPSS/H、SLAM II及SIMSCRIPT 11.5。 l介面化的模擬程式，包含AutoMod、Arena、em-plant 、 SLX、試算表軟體（增益集）及許多其他的模擬程式語言。Southern Taiwan University Graduate Program of Industrial Management19基因演算法基因演算法(1/3) Neumann（1960） 提出一個自

17、我複製的理論而奠定了基因演算法的基礎。Holland（1975）延續了Neumann的觀念發展出基因演算法（Genetic Algorithms；簡稱GA），其理論主要是根據達爾文的進化論發展而來，亦即母群體隨著世代演化競爭-物競天擇，適者生存的原理及受控變化-複製、交配、突變保留適應力較佳的染色體。 Southern Taiwan University Graduate Program of Industrial Management20基因演算法基因演算法(2/3)曾毓文（2000）基因演算法把問題的解以基因構成染色體的型態來表示，從許多的解開始進行最佳解的搜尋，藉著這些解的互相競爭，好的

18、解被複製，並且將其基因重新組合產生新的解，而差的解則會被淘汰。然後將選擇配對的父母染色體經過交配及突變產生新的候選解，此新的候選解即為繼承父母染色體部分特質的子女染色體。而新的下一代染色體會再次被評估並選來交配育種而產生更新的下一代。經由這種似自然界演化的搜尋過程之後，通常可以找到近似最佳解，甚至求得最佳解。 Southern Taiwan University Graduate Program of Industrial Management21基因演算法基因演算法(3/3)名詞定義母群體(Population)所有解集合染色體(Chromosome)每一個問題的可行解基因(Genes)染色

19、體上的基因因子適度(Fitness)目標函值演化(Evolution)搜尋的過程世代(Generation)染色體在基因與淘汰時，所產生的區間交替複製(Reproduction)將染色體複製以產生新子代族群的基因行為交配(Crossover)個染色體作基因之間的交換，來產生下一代染色體的基因行為突變(Mutation)染色體並不一定完全繼承上一代的所有特性，偶爾令子染色體的某一基因值隨意換成另一值的情形Southern Taiwan University Graduate Program of Industrial Management22基因演算法的特點基因演算法的特點 方曉嵐（1998）基

20、因演算法主要是以操作染色體來進行演化過程，在反覆演化的過程中，可看成在問題的可行區域中做系統化的多維空間搜尋；而其特點為多點搜尋、只需適應值資訊、轉移規則是隨機性而非決定性。 汪玉柏（1999）基因演算法的搜尋技術是以隨機搜尋為架構，但是基因演算法絕非僅是一種單純的隨機搜尋方法；因為基因演算法保存了演化過程中所提供的資訊，所以能展現出比單純的隨機搜尋方式更好的求解能力。Southern Taiwan University Graduate Program of Industrial Management23基因演算法的優缺點基因演算法的優缺點Lawton（1992）基因演算法的優點在於它是一種

21、穩健且有效的搜尋技術 ，使其在搜尋時不容易落入區域的局部最佳解而能夠求得比一般演算法更好的解 。 Lawton（1992）基因演算法的缺點在於計算時間長，但是此缺點也由於電腦技術的進步而漸漸的被克服了。 Southern Taiwan University Graduate Program of Industrial Management24基因演算法的演化流程基因演算法的演化流程 Lawton（1992）、Srinivas（1994）都提出不同的方法來改良基因演算法，但其基本精神都是從簡單基因演算法（SGA ,Holland 在1975 年所提出的基因演算法）發展出來的，簡單基因演算法的運作

22、過程可用下圖清楚的說明。 Southern Taiwan University Graduate Program of Industrial Management25研究方法研究方法模擬程序 基因演算法流程專案網路的建構 值例緒論緒論文獻探討文獻探討案例驗證案例驗證研究方法研究方法預期成果預期成果Southern Taiwan University Graduate Program of Industrial Management26模擬程序模擬程序 定義問題蒐集據模型建立確認模型執行模擬選擇最佳決策檢驗結果是否Southern Taiwan University Graduate Progr

23、am of Industrial Management27基因演算流程基因演算流程 編碼產生初始解複製交配設定適合度突變排序排序輸出供決策者決策是否符合終止條件是否舊染色體新染色體取代Southern Taiwan University Graduate Program of Industrial Management28專案網路的建構專案網路的建構(1/8) 以作業先行關係表示專案網路 l由於本研究是使用模擬法求解多專案排程的問題，並結合基因演算法求解最佳化的資源配置，因此先使用一個單專案的值例進行求解。 Southern Taiwan University Graduate Program

24、 of Industrial Management29專案網路的建構專案網路的建構(2/8)某建設公司剛得標一個標案，其建案為替製造商建設新廠房。其合約內容為限期47週期限內完成興建廠房的計畫，否則將會有高額的罰款。這項建造專案包含14項主要作業，而專案作業的先行關係以及其作業時間估計值如下表。Southern Taiwan University Graduate Program of Industrial Management30專案網路的建構專案網路的建構(3/8)作業作業作業名稱作業名稱前行作業前行作業作業時間估計（週）作業時間估計（週）A開挖開挖-2B地基地基A3.5C砌牆砌牆B9D屋

25、頂屋頂C5.5E外部管路外部管路C4.5F內部管路內部管路E4G外部牆板外部牆板D6.5H外部油漆外部油漆E,G8I電路工程電路工程C7.5J內部牆板內部牆板F,I9K地板地板J4L內部油漆內部油漆J5.5M外部裝置外部裝置H2N內部裝置內部裝置K,L5.5Southern Taiwan University Graduate Program of Industrial Management31專案網路的建構專案網路的建構(4/8)Southern Taiwan University Graduate Program of Industrial Management32專案網路的建構專案網路的

26、建構(5/8)由6條路徑發現路徑4為最長之工作週，花費的時間為44週。因此在最長之路徑完成，為44週，也就是在限期前3週完成。每一個作業時間都存在許多的不確定性，因此專案時間有可能大於44週，也很有可能在47週的期限後完成。有鑑於此，我們使用三點估計法作為預測值據，並計算出平均值做為模擬的依據。Southern Taiwan University Graduate Program of Industrial Management33專案網路的建構專案網路的建構(6/7)作業作業前行作業前行作業樂觀樂觀正常正常悲觀悲觀A1-12321.0 A2A123.584.53.1 A3A26918116.

27、2 A4A3,D45.5106.53.1 B1A114.553.52.2 B2B1441063.5 B3B2,F56.5117.53.1 C1A15817106.2 C2C137.596.53.1 C3C2,E39973.5 DA24485.332.3 EC115.574.53.1 FB112321.0 Southern Taiwan University Graduate Program of Industrial Management34專案網路的建構專案網路的建構(7/8)試算表建立模式方法共分為四個主要步驟： l計劃或定義問題l建構或輸入資料l測試l分析試算表模式Southern Ta

28、iwan University Graduate Program of Industrial Management35專案網路的建構專案網路的建構(8/8)依照作業先行關係，以試算表建構專案作業網路Southern Taiwan University Graduate Program of Industrial Management36值例值例(1/4)Crystal Ball模擬 lHillier & Hillier （2003）提及（Crystal Ball）軟體具有許多的因子變可同步，並能進行隨機亂的抽樣模擬，也可設定個別風險因子的機率分佈，使得目標變的模擬不再受到限制，而目標變

29、的機率分配更能讓決策者可隨著自身的需求調整，將問題化繁為簡。lCrystal Ball內建的許多機率分配，方便使用者執行模擬，諸如二項分配，幾何分配，常態分配等。除此之外，此軟體不但容易使用，更方便使用者上手，並能讓使用者輕易獲得各項統計據的輸出值，而其輸出值也可以利用圖表的方式表示。Southern Taiwan University Graduate Program of Industrial Management37值例值例(2/4)網路先行關係輸入在試算表上，並且輸入每個作業所需的作業時間。 定義輸入欄，使試算表預測各作業經過計算出專案結束的時間 。設定模擬的次，理論上模擬的次越多，則

30、模擬出的結果接近真實值的機率越大，在值例中，模擬次為1000次。Southern Taiwan University Graduate Program of Industrial Management38值例值例(3/4)Southern Taiwan University Graduate Program of Industrial Management39值例值例(4/4)結果顯示l最大專案時間為79.37週，最小專案時間為11.40週。l頻率圖指出在1000次試驗中最常出現的期間約為46週（專案的期限為47週） 。 l平均專案時間為46.22週，統計表中的平均標準誤差則為0.12週。l調

31、整頻率圖顯示專案能在47週的期限內完成的機率有60%，而有40%是超過期限47週的。 Southern Taiwan University Graduate Program of Industrial Management40案例驗證案例驗證範例問題 緒論緒論文獻探討文獻探討案例驗證案例驗證研究方法研究方法預期成果預期成果Southern Taiwan University Graduate Program of Industrial Management41案例驗證案例驗證某遊戲軟體開發公司欲開發一套新型的網路角色扮演遊戲軟體，但由於一套遊戲軟體結構與形成是極其複雜的，其牽涉到的技術層面甚廣

32、，因此須將此專案之作業項目細分為13項，並依照作業的性質對人力的職掌做配對，由於資源是有限的，因此須將其資源分配達到最佳，並成功使專案總成本降到最低。 此遊戲軟體開發的專案作業先行關係如下表，專案簽約的完成時間為45週，如超過時間則每週罰款10000元 。Southern Taiwan University Graduate Program of Industrial Management42案例驗證案例驗證作業作業前行關係前行關係作業內容說明作業內容說明A1-遊戲軟體開發專案的確認與執行遊戲軟體開發專案的確認與執行。A2A1遊戲軟體的美術企劃與設計。遊戲軟體的美術企劃與設計。A3A2美術設計

33、中的角色與場景的設計。美術設計中的角色與場景的設計。A4A3,D遊戲軟體美術部分的總整合。遊戲軟體美術部分的總整合。B1A1遊戲軟體的程式規劃與設計。遊戲軟體的程式規劃與設計。B2B1程式設計中的使用者操作設計。程式設計中的使用者操作設計。B3B2,F遊戲軟體程式部分的總整合。遊戲軟體程式部分的總整合。C1A1遊戲軟體的整體企劃提案。遊戲軟體的整體企劃提案。C2C1遊戲軟體的整體架構設計。遊戲軟體的整體架構設計。C3C2,E遊戲軟體企劃部分總整合。遊戲軟體企劃部分總整合。DA2美術設計中的動作特效設計。美術設計中的動作特效設計。EC2遊戲軟體的各項介面的設定。遊戲軟體的各項介面的設定。FB1程

34、式設計中的系統功能設定。程式設計中的系統功能設定。Southern Taiwan University Graduate Program of Industrial Management43案例驗證案例驗證根據上表，描繪網路分析圖： Southern Taiwan University Graduate Program of Industrial Management44案例驗證案例驗證遊戲軟體開發專案要順利完成的前提下，需要6種人力資源，分別為 A、B、C、D、E、F，每個種人力都允許加班，而每種人力之工作能力以每天的寫碼行來表示。6種人力的工作能力與每行的寫碼單位成本，如下表所示。 專案人

35、力專案人力不加班不加班加班加班每天寫碼行每天寫碼行每行寫碼單位成本每行寫碼單位成本每天寫碼行每天寫碼行每行寫碼單位成本每行寫碼單位成本A400$9540$13B420$10580$14C380$8520$10D360$10420$12E350$11410$10F380$9440$10Southern Taiwan University Graduate Program of Industrial Management45案例驗證案例驗證其程式碼估計如下表：程式碼估計程式碼估計人力資源人力資源專案作業專案作業樂觀樂觀最有可能最有可能悲觀悲觀AA15200540055005367 111AA226

36、60315039903267 482AA33100380046003833 511AA42600287033202930 260BB12880300032003027 116BB23220398044003867 431BB34180526060905177 664CC15250540060005550 300CC23800432050004373 418CC31880250031002493 409DD2100258032502643 404EE1980258033002620 453FF2650327041503357 529Southern Taiwan University Gradu

37、ate Program of Industrial Management46案例驗證案例驗證決策目標的成本模式如下所示： mjjjRCTLDCDTCTPC1)()(PC = 專案總成本CT = 專案的完成時間DC = 專案延遲的罰款/天DT = 專案完工最後期限TLj = 在專案的資源j下的每行寫碼總行RCj = 在專案的資源j下的每行寫碼單位成本m = 專業人力的種 Southern Taiwan University Graduate Program of Industrial Management47案例驗證案例驗證建立試算表模式 Southern Taiwan University G

38、raduate Program of Industrial Management48案例驗證案例驗證L欄表示每個人力每天可寫碼的行，根據B21可改變加班代碼，並參照另一個表的代碼做計算。 依據加班代碼使用VLOOKUP陣列搜尋的方式，從另外一張試算表64種不同的加班組合所造成的每天寫碼行陣列搜尋，並傳回原本的試算表格中， 如下圖所示。 Southern Taiwan University Graduate Program of Industrial Management49案例驗證案例驗證Southern Taiwan University Graduate Program of Industrial Management50案例驗證案例驗證依據每項作業的先行關係建立在試算表上，並在具有先行作業的作業上，加上試算表Max的函，如下圖所示。Southern Taiwan University Graduate Program of Industrial Management51案例驗證案例驗證將試算表中建立的學模式進行模擬試驗1000次，會得到一個最佳排程策略與最小化總成本，從下表可以得知，最小化成本的組合為資源A1、B1、C1、D1、E2、F1成本為431033元，並且能在期限之內完成（45週）。 Sou