雙資源限制下之專案排程研究

Project Scheduling with Respect to Double Resources Constrained

傳統的專案排程作業大多以計畫評核術(program evaluation and review technique, PERT)或要徑法(critical path method, CPM)進行。然而，無論是計畫評核術或要徑法皆以資源無限為前提，俾使專案能在最短時間內完成，事實上資源不可能無限，而完工時間也不是單一的衡量準則。本研究旨在探討雙重資源限制下之專案排程問題，考慮資源為可恢復性，求取資源使用率最大之最小總工期。因為問題本質為NP-hard，因此，本研究以模擬多個CPU的概念，建構改良式平行塔布搜尋程序，使塔布搜尋能夠更全面性，並能避免重複搜尋，以確保求解的速率與品質。 模擬測試資料採自國際線上測試題庫(project scheduling problem library, PSPLIB )，作業數設定為30, 60, 90及120四種，每種作業數測試30組例題。測試結果顯示本研究建構之改良式平行塔布搜尋法具有快速求解能力，更重要的是求解品質與穩定度兩方面，表現都較一般塔布搜尋法優異。此外，研究發現CPU總數越多，求解品質與穩定度也相對較佳，但是求解時間則會明顯遞增，當CPU總數為40時最能兼顧求解品質與時間效率。