在專案排程中，專案經理人如何掌握影響專案運行的因素來安排行程是一重要之管理議題。以現今的排程而言，可能會因為外包而必須將時間限制和不確定因素也列入考慮。時間限制係指和外包商簽約決定交貨的時間可能具有時窗範圍或時間排程等等限制；而外包商又可能會因毀約或延遲交貨等不確定因素而影響到專案活動的排程規劃，導致專案活動成本增加甚至停擺。本論文旨在探討如何在時間限制之下，對專案排程的活動開始時間加入額外的時間彈性，建立一具時間限制之穩定性專案基線排程以將排程的不確定性所引起之損失最小化。首先，我們改良文獻中的隨機專案排程網路產生器，將額外的時窗與時間排程限制同時列入考慮以設計一個新的具時間限制之隨機專案排程網路產生器。接著，本研究提出兩種多項式時間的啟發式演算法：貪婪演算法一(Greedy I) 及貪婪演算法二(Greedy II)來求解。其中貪婪演算法一乃依本模式之網路圖和限制式特性為基礎發展而得；而貪婪演算法二更進一步加入成本的考量來設計排程時間該如何去調整，以得到更佳之排程結果。雖然此兩種啟發式演算法有不錯的求解效率，其求解效果卻不甚理想。最後，我們亦設計了另一個基因演算法來規劃排程，並與CPLEX最佳化軟體比對求解效率與效果，我們發現基因演算法在適當的終止條件設定下，可以得到不錯的解，且其求解效率在大規模的排程問題上亦遠勝CPLEX。

In this thesis, we first propose a random project scheduling network generator by integrating additional time window or time schedule constraints with a popular project network generator (RanGen). We then give two polynomial heuristic algorithms (Greedy I and Greedy II) to solve the integer programming problems, where Greedy I exploits the special structure of the models so that it can suggest a feasible start time for each task in a topological order to reduce the objective values, while Greedy II further takes the objective weights associated with variables into consideration and improves the quality of the solutions obtained by Greedy I. To further get solutions of better qualities, we propose a genetic algorithm and conduct computational experiments to evaluate the effectiveness (optimality gap) and efficiency (running time) of our proposed algorithms (Greedy I, Greedy II, and GA) and a popular optimization solver, CPLEX. The results show that our greedy heuristics are very efficient but not as effective, GA can be both efficient and effective, while CPLEX usually consumes much more computational time and is especially inefficient for problems of larger scale.

Adelson-Velsky, G. M. and Levener, E. Project scheduling in and-or graphs: A generalization of dijkstra's algorithm. Mathematics of Operations Research, 27(3),
504-517, 2002.

Agrawal, M. K., Elmaghraby, S. E. and Herroelen, W. Dagen: a generator of testsets for project activity nets. European Journal of Operational Research, 90, 376-382,
1996.

Bein, W. W., Kaburowski, J. and Stallmann, M. F. M. Optimal reduction of twoterminal directed acyclic graphs. Society for Industrial and Applied Mathematics Journal on Computing, 21, 1112-1129, 1992.

Bey, R. B., Doersch, R. and H., P. J. The net present value criterion: its impact on project scheduling. Project Management Quarterly, 12(2), 35-45, 1981.

Bowers, J. A. Criticality in resource constrained networks. Journal of the Operational Research Society, 46, 80-91, 1995.

Calhoun, K. M., Deckro, R. F., Moore, J. T., Chrissis, J. W. and Van Hove, J. C. Planning and re-planning in project and production planning. Omega(30), 155–170, 2002.

Chen, Y. L., Rinks, D. and Tang, K. Critical path in an activity network with time constraints. European Journal of Operational Research, 100, 122-133, 1997.

Crowston, W. Decision cpm: Network reduction and solution. Operations Research Quarterly, 21(40), 435-445, 1970.

Davis, E. W. An experimental investigation of resource allocation in multiativity projets. Operational Research, 24, 587-591, 1973.

Demelemeester, E., Vanhoucke, M. and Herroelen, W. Rangen: A random network generator for activity-on-the-node networks. Journal of Scheduling, 6, 17-38, 2003.

Demeulemeester, E. B., Dodin and Herroelen, W. A random activity network genertor. Operations Research, 41, 972-980, 1993.

Elmaghraby, S. E. Activity network: project planning and control by network models.New York: Wiley, 1997.

Elmaghraby, S. E. and S., H. W. On the measurement of complexity in activity networks. European Journal of Operational Research, 5, 223-234, 1980.

El Sakkout, H. and Wallace, M. Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints 5, 4, 359–388, 2000.

Gillies, D. and Liu, J. Scheduling tasks with and/or precedence constraints. Society for Industrial and Applied Mathematics Journal on Computing, 24(4), 787-810,
1995.

Goldwasser, M. H. and Motwani, R. Complexity measures for assembly sequences. International Journal of Computational Geometry and Applications, 9, 371-418, 1999.

Hall, N. and Posner, M. 2000. Sensitivity analysis for intractable scheduling problems. Research paper, The Ohio State University.

Hapke, M., Jaskievicz, A. and Slowinski, R. Fuzzy multimode resource-constrained project scheduling with multiple objectives. in: Weglarz, j. (ed.), project scheduling : Recent models, algorithms and applications. Kluwer Academic Publishers, 1999.

Herroelen, W. and Leus, R. The construction of stable project baseline schedules. European Journal of Operational Research, 156, 550-565, 2004.

Herroelen, W. and Leus, R. Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165, 289-306, 2005.
Hillier, F. S. and Lieberman, G. J. Introduction to operations research. McGraw-Hill, 2001.

Icmeli-Tuket, O. and Rom, W. O. Ensuring quality in resource constrained project scheduling. European Journal of Operational Research, 103, 483-496, 1997.

Igelmund, G. and Radermacher, F. J. Algorithmic approaches to preselective strategies for stochastic scheduling problems. Networks(13), 1-28, 1983.

Kolisch, R. and Padman, R. An integrated survey of deterministic project scheduling. Omega, 29(3), 249-272, 2001.

Kolisch, R., Sprecher, A. and Drexl, A. Characterization and generation of a general class of resource-constrained project scheduling problems. The Institute of Management Sciences, 41, 1693-1703, 1995.

Leon, V., Wu, S. and Storer, R. Robustness measures and robust sheduling for job shops. Institute of Industrial Engineers transactions, 26(5), 32-43, 1994.

Mastor, A. A. An experimental and compararive evaluation of production ine balancing techniques. The Institute of Management Sciences, 16, 728-746, 1970

Methta, S. V. and Uzsoy, R. M. Predictable scheduling of job shop subject to breakdowns. Institute of Electrical and Electronics Engineers Transactions on Robotics
and Automation, 14(3), 365-378, 1998.

Pascoe, T. L. Allocation of resources -cpm. Revue francaise de Recherche Operationelle, 38, 31-38, 1966.

Patterson, J. H. A comparison of exact procedures for solving the multiple constrained resource project scheduling problem. The Institute of Management Sciences, 20, 767-784, 1984.

Prabuddha, D., Dunne, E. J. and Ghosh, C., J. B. andWell. The discrete time-cost tradeo® problem for project networks. European Journal of Operational Research,
81, 225-238, 1995.

Radermacher, F. J. Scheduling of project networks. Annals of Operations Research(4), 227-252, 1985.

Rommelfanger, H. Fulpal: An interactive method for solving (multiobjective) fuzzy linear programming problems.in: Slowinski, r., teghem, j. (eds.), stochastic versus
fuzzy approaches to multiobjective mathematical programming under uncertainty. Kluwer Academic Publishers, 1990.

Sadeh, S., N. amd Otsuka and Schelback, R. 1993. Predictive and reactive scheduling with the microboss production scheduling and control system. (Tech. Rep.). Pro
ceedings of the IJCAI-93 Workshop on Knowledge-based Production Planning,Scheduling.

Schwindt, C. 1995. A new problem generator for di®erent resource-constrained project
scheduling problems with minimal and maximal time lags (Tech. Rep.). University of Karlsruhe: WIOR-Report-449, Institut fur Wirtschaftstheorie und Operations
Research.

Skutella, M. Approximation algorithms for the discrete time-cost tradeo® problem. Mathematics of Operations Research, 23(4), 909-929, 1998.

Stork, F. 2000. Branch-and-bound algorithms for stochastic resource-constrained project scheduling. (Research Report No. 702/2000.). Technische Universitat Berlin.

Tavares, V., Ferreira, J. A. A. and Coelho, S. J. On the optimal management of project risk. European Journal of Operational Reserch, 107, 451-469, 1998.