<p> KARNOUB, RAZEK E. An Exact Bidirectional Approach to the Resource Constrained Project Scheduling Problem. (Under the direction of Salah E. Elmaghraby) The aim of this research is to develop a new approach to the Resource Constrained Project Scheduling Problem. Traditionally, most exact approaches to solve the problem have been either Integer Programming approaches or Branch and Bound (BaB) ones. Of the two, BaB procedures have proven to be the more successful computationally. But, while it is quite intuitive to conceive that the root node of a BaB search tree should be the start activity, it is no less conceivable that it be the terminal activity. Indeed, it is conceivable that the search starts from both ends and concludes somewhere in the middle of the ensuing trees. Unfortunately, BaB as a methodology is not amenable to deriving a termination criterion for such a procedure which guarantees optimality. To a large extent, this research can be seen as an attempt at accomplishing just that. We start with a comprehensive review of the literature related to the problem. We present a new Integer Programming model to describe it together with a `look-ahead' heuristic procedure which may be used along with it. The main advantage of this procedure is its ability to reflect planning over the short horizon in anticipation of changes to the project in the more future. Our chief contribution is in the third part of this study which sets up the problem as a Shortest Path Problem in two `state networks', forward and reverse, where the nodes reflect the precedence feasibility or partial completion of the activities of the project. We develop the conceptual tools to construct the networks and to properly detect a `path' between their sources from which a makespan optimal schedule could be derived. The theoretical constructs ultimately result in algorithms that solve the problem proceeding forward, in reverse, or bidirectionally. These algorithms have been tested on the J30 benchmark data set of Kolisch, Sprecher and Drexl (1995). Computational results show important advantages of the bidirectional approach but also point out significant avenues for improvement.<P>
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-20020110-201041 |
| Date | 30 January 2002 |
| Creators | Karnoub, Razek E. |
| Contributors | Dr. Salah E. Elmaghraby, Dr. Bibhuti B. Bhattacharyya, Dr. Carla D. Savage, Dr. Hien T. Tran |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-20020110-201041 |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0051 seconds