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

Project Scheduling with Respect to Double Resources Constrained

10.30136/ZXYGLKX.201006.0001

黃榮華；楊長林

資源限制 ； 專案排程 ； 平行塔布搜尋程序 ； 總工期 ； Resources Constrained ； Project Scheduling ； Parallel Tabu Search ； Total Completion Time

資訊與管理科學

3卷1期（2010 / 06 / 30）

1 - 16

繁體中文

傳統的專案排程作業大多以計畫評核術(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時最能兼顧求解品質與時間效率。

The traditional project scheduling operations are mostly engaged with PERT (program evaluation and review technique) or CPM (critical path method). However, both PERT and CPM presume infinite resources in order to complete the project within the shortest time range. As a matter of fact, it's impossible that resources are infinite, and the time range of completion is not the only standard of measurement. Our research probes into the project scheduling problem limited by double resources. Considering that resources are restorable, we look for the minimal total completion time with maximized rate of resource utility. Since the nature of the problem is NP-hard, therefore, we construct the searching process of improved Parallel Tabu Search by the concept of simulating multiple CPUs, in order to make the improved Tabu Search more comprehensive and avoid repeated searching to ensure the speed and quality of the solution. The testing data is taken from PSPLIB (project scheduling problem library). The numbers of the activities are set as 30, 60, 90 and 120, each tests thirty different samples. The result of the test reveals that the improved Parallel Tabu Search constructed by our research has the capability of fast solving. More importantly, the performances of both quality and stability of the solution are superior to the original Tabu Search. In addition, the more the CPUs are, the better both quality and stability of the solution comparatively get, but the solving time apparently increases. When the total number of the CPU is forty, it obtains the best result in the solving quality and efficiency.

1. Bozejko, W.,Wodecki, M.(2004).Parallel Tabu Search Method Approach for Very Difficult Permutation Scheduling Problems.PARELEC,156-161.
2. Cogill, R.,Hindi, H.(2007).Optimal Routing and Scheduling in Flexible Manufacturing Systems Using Integer Programming.IEEE Conference on Decision and Control
3. Davis, E.W.,Patterson, J.H.(1975).A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling.Management Science,21,944-955.
4. Dorigo, M.,Gambardella, L.M.(1997).Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.IEEE Transactions on Evolutionary Computation,1,53-66.
5. Driessen, B. J.,Kwok, K. S.(1998).A Multi-objective Dynamic Programming Approach to Constrained Discrete-time Optimal Control.Proceedings of the American Control Conference
6. Fiechter, C.N.(1994).A Parallel Tabu Search Algorithm for Large Traveling Salesman Problems.Discrete Applied Mathematics,51,243-267.
7. Glover, F.(1977).Tabu Search.Boston:Kluwer Academic Publishers.
8. Heizer, J.,Render, B.(2006).Principles of Operations Management.New Jersey:Pearson Education.
9. Holland, J.H.(1975).Adaptation in Natural and Artificial System.University of Michigan Press.
10. Huang, K.L.,Liao, C.J.(2008).Ant Colony Optimization Combined with Taboo Search for the Job Shop Scheduling Problem.Computers & Operations Research,35,1030-1046.
11. Kelley, J.E.(1963).The Critical Path Method: Resources Planning and Scheduling.Industrial Scheduling,New Jersey:
12. Kirkpatrick, S.,Gelatt, C.D.,Vecchi, M.P.(1983).Optimization by Simulated Annealing.Science,220(4598),671-679.
13. Low, C.(2005).Simulated Annealing Heuristic for Flow Shop Scheduling Problems with Unrelated Parallel Machines.Computers & Operations Research,32,2013-2025.
14. Nababan, E.B.,Hamdan, A.R.,Abdullah, S.,Zakaria, M.S.(2008).Branch and Bound Algorithm in Optimizing Job Shop Scheduling Problems.International Symposium on Information Technology,1,1-5.
15. Ozcan, E.,Onbasioglu, E.(2004).Genetic Algorithms for Parallel Code Optimization.Evolutionary Computation,2,1375-1381.
16. Tague, P.,Slater,D.,Poovendran, R.,Noubir, G.(2008).Linear Programming Models for Jamming Attacks on Network Traffic Flows.International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops,207-216.
17. Taillard, E.(1994).Parallel Taboo Search Techniques for the Job Shop Scheduling Problem.ORSA Journal on Computing,6(2),108-117.
18. Taillard, E.(1991).Robust Taboo Search for the Quadratic Assignment Problem.Parallel Computing,17,443-445.
19. Viniotis, I.,Ephremides, A.(1988).Linear Programming as a Technique for Optimization of Queueing Systems.IEEE Conference on Decision and Control Proceedings of the 27th,1,652-656.
20. Wiest, J.D.(1963).Carnegie Institute of Technology.