現在位置首頁 > 博碩士論文 > 詳目
  • 同意授權
論文中文名稱:應用分枝界限法解決資源具有限性下的專案選擇與排程問題 [以論文名稱查詢館藏系統]
論文英文名稱:Resource-constrained project selection and scheduling problem using a branch and bound method [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:工業工程與管理研究所
畢業學年度:97
出版年度:98
中文姓名:尹新瀚
英文姓名:Shin-Han Ying
研究生學號:96378049
學位類別:碩士
語文別:中文
口試日期:2009-06-29
論文頁數:39
指導教授中文名:吳建文
口試委員中文名:邱垂昱;黃祥熙
中文關鍵詞:專案選擇列舉法資源有限的專案規劃分枝界限法
英文關鍵詞:Project scheduling problemRCPSPBranch and bound method
論文中文摘要:近代,專案排程問題是一個相當被重視的問題,許多與該主題有關的研究與文獻相繼地提出,不過早期的排程問題通常假設活動排程時所需要的各種資源數量為無限下的最佳化研究,不過這樣的假設並不符合現實的狀況,因此自60年代提出資源有限下的專案排程問題後,這樣的問題便更受到學者們的重視。
資源有限下的專案排程問題(簡稱RCPSP問題)被證明為一種NP-Hard問題,而在RCPSP問題中使用分枝界限法是一種尋找最佳解的好方法。因此本研究透過列舉與分枝界限法分別解決專案的選擇與排程問題。列舉程序每次列舉一種專案組合,並透過分枝界限法找出該組合的最佳排程解,我們假設該專案的利潤函數與其完成時間有關,在排程完畢後便可得到該組合的最大利潤,透過各組合下的利潤比較得到具有最大利潤的專案組合與規劃結果,供專案經理作為決策依據。而實驗結果亦證明列舉法結合分枝界限法可以獲得較高的利潤。
論文英文摘要: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.
論文目次:中文摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 1
1.3 研究範圍 2
1.4 研究流程 2
第二章 文獻探討 4
2.1 資源有限的排程問題之發展過程、定義與分類 4
2.1.1 RCPSP問題的發展過程 4
2.1.2 RCPSP問題的定義 5
2.1.3資源有限的排程問題分類 6
2.2 RCPSP問題的最佳解法與啟發式演算法 6
2.2.1 RCPSP問題的最佳解法 6
2.2.2 RCPSP問題的啟發法 8
2.3 其餘目標函式的RCPSP問題 12
第三章 研究方法 14
3.1 基本假設 14
3.2 參數定義與模型建立 15
3.2.1 參數定義 15
3.2.2 數學模型 16
3.3 研究方法 17
3.3.1 輸入與輸出系統 17
3.3.2 列舉系統 18
3.3.3 排程系統 19
第四章 實驗設計與實驗結果 27
4.1 實驗設計與參數說明 27
4.2 實驗結果 28
第五章 結論與建議 32
5.1 結論 32
5.2 後續研究與建議 32
參考文獻 34
論文參考文獻:[1] Baker, K.R., Introduction to sequencing and scheduling, New York: John Wiley & Sons, 1974, pp. 51-58.
[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.
[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.
[4] Gen, M., and Cheng, R., Genetic algorithms and engineering design , New York: Wiley-Interscience, 1997, pp. 12-16.
[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
[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
[7] Boctor, F., “Some efficient multi-heuristic procedures for resource-constrained project scheduling. Euro”, J. Opl. Res, 1990, vol.49, pp. 3-13
[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
[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
[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
[11] Chen, P.H., and Weng, H., “A two-phase GA model for resource-constrained project scheduling”, Automation in Construction, 2008
[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
[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
[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
[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
[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
[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
[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
[19] Demeulemeester, E.L., and Herroelen, W.S. , “New benchmark results for the resource-constrained project scheduling problem”, Management Science, 1997, pp. 1485-1492
[20] Elsayed, E.A. , “Algorithms for project scheduling with resource constraints”, International Journal of Production Research, 1982, vol.20, no.1, pp. 95-103
[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
[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
[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
[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
[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
[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
[27] Johnson, R.V. , “Optimally balancing large assembly lines with 'FABLE'”, Management Science, 1988, pp. 240-253
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[38] Pascoe, T.L., “Allocation of resources-CPM”, Revue Francaise de Recherche Operationelle, 1966, vol.38, pp. 31-38
[39] Patterson, J.H., “Alternate methods of project scheduling with limited resources”, Naval Research Logistics Quarterly, 1973, vol.20, no.4
[40] Patterson, J.H. , “Project scheduling: The effects of problem structure on heuristic performance”, Naval Research Logistics Quarterly, 1976, vol.23, no.1
[41] Patterson, J.H. , “A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem”, Management Science, 1984, pp. 854-867
[42] Russell, A.H. , “Cash flows in networks”, Management Science, 1970, pp. 357-373
[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
[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
[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
[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
[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
[48] Thesen, A., ”Heuristic scheduling of activities under resource and precedence restrictions”, Management Science, 1976, pp. 412-422
[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
[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
[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
[52] Wiest, J.D., “A heuristic model for scheduling large projects with limited resources”, Management Science, 1967, pp. 359-377
[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
[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
[55] Johnson, T.J.R., An algorithm for the resource-constrained project scheduling problem, unpublished Ph. D. thesis, Massachusetts Institute of Technology, 1967
論文全文使用權限:同意授權於2009-08-06起公開