Title

應用分枝界限法解決資源具有限性下的專案選擇與排程問題

Translated Titles

Resource-constrained project selection and scheduling problem using a branch and bound method

DOI

10.6841/NTUT.2009.00625

Authors

尹新瀚

Key Words

專案選擇 ; 列舉法 ; 資源有限的專案規劃 ; 分枝界限法 ; Project scheduling problem ; RCPSP ; Branch and bound method

PublicationName

臺北科技大學工業工程與管理系碩士班學位論文

Volume or Term/Year and Month of Publication

2009年

Academic Degree Category

碩士

Advisor

吳建文

Content Language

繁體中文

Chinese Abstract

近代,專案排程問題是一個相當被重視的問題,許多與該主題有關的研究與文獻相繼地提出,不過早期的排程問題通常假設活動排程時所需要的各種資源數量為無限下的最佳化研究,不過這樣的假設並不符合現實的狀況,因此自60年代提出資源有限下的專案排程問題後,這樣的問題便更受到學者們的重視。 資源有限下的專案排程問題(簡稱RCPSP問題)被證明為一種NP-Hard問題,而在RCPSP問題中使用分枝界限法是一種尋找最佳解的好方法。因此本研究透過列舉與分枝界限法分別解決專案的選擇與排程問題。列舉程序每次列舉一種專案組合,並透過分枝界限法找出該組合的最佳排程解,我們假設該專案的利潤函數與其完成時間有關,在排程完畢後便可得到該組合的最大利潤,透過各組合下的利潤比較得到具有最大利潤的專案組合與規劃結果,供專案經理作為決策依據。而實驗結果亦證明列舉法結合分枝界限法可以獲得較高的利潤。

English Abstract

Project scheduling problem is an old well known problem. There is a lot of literature related to this problem. In last forty years, project scheduling problem with resource constraint has attracted more attention to researchers. Resource-constrained project scheduling problem(RCPSP)has been proved to be a NP-hard problem . Many methods had been used to find the optimal solution . The branch and bound method is one of the efficient methods. In our thesis, we combine an explicit enumeration procedure and the branch and bound method for solving RCPSP and project selection problem simultaneously. In our approach, we enumerate all combinations of projects and use the branch and bound method to schedule the selected projects. In each step of enumeration, we calculate the project profit of this combination. Finally, we can provide maximum profit for decision maker who needs to select the most profitable projects to execute. The experiment result in this paper shows that our approach gives better solution than other heuristic methods.

Topic Category 管理學院 > 工業工程與管理系碩士班
工程學 > 工程學總論
社會科學 > 管理學
Reference
  1. [5] Alvarez-Valdes, R., and Tamarit, J.M., “Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis”, Advances in project scheduling, 1989, pp.134
    連結:
  2. [6] Blazewicz, J., Lenstra, J.K., and Rinnooy Kan, A.H.G., “Scheduling subject to resource constraints: Classification and complexity”, Discrete Appl. Math., 1983, vol.5, no.1, pp. 11-24
    連結:
  3. [7] Boctor, F., “Some efficient multi-heuristic procedures for resource-constrained project scheduling. Euro”, J. Opl. Res, 1990, vol.49, pp. 3-13
    連結:
  4. [8] Bouleimen, K., and Lecocq, H., ”A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version”, European Journal of Operational Research, 2003, vol.149, no.2, pp. 268-281
    連結:
  5. [9] Brucker, P., Knust, S., Schoo, A., and Thiele, O., ”A branch and bound algorithm for the resource-constrained project scheduling problem”, European Journal of Operational Research, 1998, vol.107, no.2 , pp. 272-288
    連結:
  6. [10] Brucker, P., Drexl, A., Mohring, R., Neumann, K., and Pesch, E., “Resource-constrained project scheduling: Notation, classification, models, and methods”, European Journal of Operational Research, 1999, vol.112, no.1, pp. 3-41
    連結:
  7. [11] Chen, P.H., and Weng, H., “A two-phase GA model for resource-constrained project scheduling”, Automation in Construction, 2008
    連結:
  8. [12] Chen, J., and Askin, R.G. , “Project selection, scheduling and resource allocation with time dependent returns”, European Journal of Operational Research, 2009, vol.193, no.1, pp. 23-34
    連結:
  9. [13] Christofides, N., Alvarez-Valdes, R., and Tamarit, J.M. , “Project scheduling with resource constraints: A branch and bound approach”, European Journal of Operational Research, 1987, vol.29, no.3, pp. 262-273
    連結:
  10. [15] Damaka, N., Jarboui, B., Siarry, P., and Loukil, T. , “Differential evolution for solving multi-mode resource-constrained project scheduling problems”, Computers and Operations Research, 2009, vol.36, no.9, pp. 2653-2659
    連結:
  11. [16] Davis, E.W., and Patterson, J.H. , “A comparison of heuristic and optimum solutions in resource-constrained project scheduling’, Management Science, 1975, pp. 944-955
    連結:
  12. [17] Demassey, S., Artigues, C., and Michelon, P. , “Constraint-propagation-based cutting planes: An application to the resource-constrained project scheduling problem”, INFORMS Journal on computing, 2005, vol.17, no.1, pp. 52-65
    連結:
  13. [18] Demeulemeester, E., and Herroelen, W. , “A branch-and-bound procedure for the multiple resource-constrained project scheduling problem”, Management Science, 1992, pp. 1803-1818
    連結:
  14. [19] Demeulemeester, E.L., and Herroelen, W.S. , “New benchmark results for the resource-constrained project scheduling problem”, Management Science, 1997, pp. 1485-1492
    連結:
  15. [20] Elsayed, E.A. , “Algorithms for project scheduling with resource constraints”, International Journal of Production Research, 1982, vol.20, no.1, pp. 95-103
    連結:
  16. [22] Feng, C.W. , “Using genetic algorithms to solve construction time-cost trade-off problems”, Journal of computing in civil engineering, 1997, vol.11, pp. 184
    連結:
  17. [23] Forney, W.R., Robinson, S.J., and Pascoe, D.J. , “Congenital heart disease, deafness, and skeletal malformations: a new syndrome?”, The Journal of pediatrics, 1966, vol.68, no.1, pp. 14
    連結:
  18. [24] Herroelen, W.S., Van Dommelen, P., and Demeulemeester, E.L. , “Project network models with discounted cash flows a guided tour through recent developments”, European Journal of Operational Research, 1997, vol.100, no.1, pp. 97-121
    連結:
  19. [25] Herroelen, W., De Reyck, B., and Demeulemeester, E. , “Resource-constrained project scheduling: a survey of recent developments”, Computers and Operations Research, 1998, vol.25, no.4, pp. 279-302
    連結:
  20. [26] Jarboui, B., Damak, N., Siarry, P., and Rebai, A. , “A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems”, Applied Mathematics and Computation, 2008, vol.195, no.1, pp. 299-308
    連結:
  21. [27] Johnson, R.V. , “Optimally balancing large assembly lines with 'FABLE'”, Management Science, 1988, pp. 240-253
    連結:
  22. [28] Kolisch, R., Sprecher, A., and Drexl, A. , “Characterization and generation of a general class of resource-constrained project scheduling problems”, Management Science, 1995, pp. 1693-1703
    連結:
  23. [29] Kolisch, R. , “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation”, European Journal of Operational Research, 1996, vol.90, no.2, pp. 320-333
    連結:
  24. [30] Kolisch, R., and Hartmann, S. , “Experimental investigation of heuristics for resource-constrained project scheduling: An update”, European Journal of Operational Research, 2006, vol.174, no.1, pp. 23-37
    連結:
  25. [32] Leu, S.S., Chen, A.T., and Yang, C.H., “A GA-based fuzzy optimal model for construction time–cost trade-off”, International Journal of Project Management, 2001, vol.19, no.1, pp. 47-58
    連結:
  26. [34] Merkle, D., Middendorf, M., and Schmeck, H., “Ant colony optimization for resource-constrained project scheduling”, IEEE Transactions on Evolutionary Computation, 2002, vol.6, no.4, pp. 333-346
    連結:
  27. [35] Mingozzi, A., Maniezzo, V., Ricciardelli, S., and Bianco, L., ”An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation”, Management Science, 1998, pp. 714-729
    連結:
  28. [36] Mohring, R.H., “Algorithmic aspects of comparability graphs and interval graphs”, Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications, 1984, pp. 41–102
    連結:
  29. [38] Pascoe, T.L., “Allocation of resources-CPM”, Revue Francaise de Recherche Operationelle, 1966, vol.38, pp. 31-38
    連結:
  30. [39] Patterson, J.H., “Alternate methods of project scheduling with limited resources”, Naval Research Logistics Quarterly, 1973, vol.20, no.4
    連結:
  31. [40] Patterson, J.H. , “Project scheduling: The effects of problem structure on heuristic performance”, Naval Research Logistics Quarterly, 1976, vol.23, no.1
    連結:
  32. [41] Patterson, J.H. , “A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem”, Management Science, 1984, pp. 854-867
    連結:
  33. [42] Russell, A.H. , “Cash flows in networks”, Management Science, 1970, pp. 357-373
    連結:
  34. [44] Sprecher, A., Hartmann, S., and Drexl, A., “An exact algorithm for project scheduling with multiple modes”, OR Spectrum, 1997, vol.19, no.3, pp. 195-203
    連結:
  35. [45] Sprecher, A., and Drexl, A., “Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm”, European Journal of Operational Research, 1998, vol.107, no.2, pp. 431-450
    連結:
  36. [46] Stinson, J.P., Davis, E.W., and Khumawala, B.M., “Multiple Resource–Constrained Scheduling Using Branch and Bound”, IIE Transactions, 1978, vol.10, no.3, pp. 252-259
    連結:
  37. [47] Storn, R., and Price, K., “Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces”, INTERNATIONAL COMPUTER SCIENCE INSTITUTE-PUBLICATIONS-TR, 1995, vol.12,no.4, pp. 282-289
    連結:
  38. [48] Thesen, A., ”Heuristic scheduling of activities under resource and precedence restrictions”, Management Science, 1976, pp. 412-422
    連結:
  39. [49] Ulusoy, G., and Zdamar, O., “L., 1989, Heuristic performance and network/resource characteristics in resourceconstrained project scheduling”, Journal of the Operational Research Society, vol.40, pp. 1145-1152
    連結:
  40. [51] Whitehouse, G.E., and Brown, J.R., ”GENRES: An extension of Brooks algorithm for project scheduling with resource constraints”, Computers and Industrial Engineering, 1979, vol.3, no.4, pp. 261-268
    連結:
  41. [52] Wiest, J.D., “A heuristic model for scheduling large projects with limited resources”, Management Science, 1967, pp. 359-377
    連結:
  42. [55] Johnson, T.J.R., An algorithm for the resource-constrained project scheduling problem, unpublished Ph. D. thesis, Massachusetts Institute of Technology, 1967
    連結:
  43. [1] Baker, K.R., Introduction to sequencing and scheduling, New York: John Wiley & Sons, 1974, pp. 51-58.
  44. [2] Cooper, O., Dassie, A.J.W., and Lawson, P.M.A., Motivating Black Students to Read Beyond the Regular School Day , New York: John Wiley & Sons, 1976 , pp. 41-50.
  45. [3] De Reyck, B. , Scheduling projects with generalized precedence relations: Exact and heuristic procedures, Katholieke Universiteit Leuven: Faculteit Economische en Toegepaste Economische Wetenschappen, 1998, pp. 45-49.
  46. [4] Gen, M., and Cheng, R., Genetic algorithms and engineering design , New York: Wiley-Interscience, 1997, pp. 12-16.
  47. [14] Colorni, A., Dorigo, M., and Maniezzo, V. , “Ant colony system for job-shop scheduling”, Belgian Journal of Operations Research Statistics and Computer Science, 1994, vol.34, no.1, pp. 39-53
  48. [21] Fehler, D. , “Die Variationen-Enumeration—Ein Naherungsverfahren zur Planung des optimalen Betriebsmitteleinsatzes bei der Terminierung von Projekten”, Elektronische Datenverarbeitung, 1969, vol.10, pp. 479–483
  49. [31] Lawrence, S.R. , “Resource constrained project scheduling–A computational comparison of heuristic scheduling techniques”, Technical report, Graduate School of Industrial Administration, CarnegieMellon University, 1985, vol.174, no.1, pp. 23-37
  50. [33] Macatonia, S.E., Patterson, S., and Knight, S.C., “Suppression of immune responses by dendritic cells infected with HIV”, Immunology, 1989, vol.67, no.3, pp. 285
  51. [37] Muller-Merbach, H., “Ein Verfahren zur Planung des optimalen Betriebsmitteleinsatzes bei der Terminierung von Grosprojekten”, Zeitschrift fur wirtschaftliche Fertigung, 1967, vol.62, no.2
  52. [43] Sprecher, A., Hartmann, S., and Drexl, A. , “Project scheduling with discrete timeresource and resource-resource tradeoffs”. Manuskripte aus den Instituten fur Betriebswirtschaftslehre, 1994 , pp. 357-373
  53. [50] Valls, V., Perez, M.A., and Quintanilla, M.S., “Heuristic performance in large resource-constrained projects”, Department D’Estadistica I Invecigacio Operativa, Universitat de Valencia Tech. Rep, 1992, pp. 92-92
  54. [53] Bauer, A., Bullnheimer, B., Hartl, R.F., and Strauss, C., “An ant colony optimization approach for the single machine total tardiness problem”, Book An ant colony optimization approach for the single machine total tardiness problem , Citeseer, 1999, pp. 1445–1450
  55. [54] Gonguet, L., “Comparison of three heuristic procedures for allocating resources and producing schedule”, Book Comparison of three heuristic procedures for allocating resources and producing schedule, North-Holland, 1969, pp. 249