TITLE

A BRANCH-AND-BOUND PROCEDURE FOR THE MULTIPLE RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM

AUTHOR(S)
Demeulemeester, Erik; Herroelen, Willy
PUB. DATE
December 1992
SOURCE
Management Science;Dec1992, Vol. 38 Issue 12, p1803
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
In this paper a branch-and-bound procedure is described for scheduling the activities of a project of the PERT/CPM variety subject to precedence and resource constraints where the objective is to minimize project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. Precedence and resource-based bounds described in the paper are combined with new dominance pruning rules to rapidly fathom major portions of the solution tree. The procedure is programmed in the C language for use on both a mainframe and a personal computer. The procedure has been validated using a standard set of test problems with between 7 and 50 activities requiring up to three resource types each. Computational experience on a personal computer indicates that the procedure is 11.6 times faster than the most rapid solution procedure reported in the literature while requiring less computer storage. Moreover, problems requiring large amounts of computer time using existing approaches for solving this problem type are rapidly solved with our procedure using the dominance rules described, resulting in a significant reduction in the variability in solution times as well.
ACCESSION #
4731839

 

Related Articles

  • AN IMPLICIT ENUMERATION ALGORITHM FOR THE MACHINE SEQUENCING PROBLEM. Florian, M.; Trepant, P.; McMahon, G. // Management Science;Aug1971, Vol. 17 Issue 12, pB-782 

    An implicit enumeration algorithm is developed for the machine sequencing problem. The method is based on the graph-theoretical representation of the problem. The convergence of the algorithm is demonstrated, and its efficiency is evaluated by experiments carried out with a code written for the...

  • PROGRAM EVALUATION AND REVIEW TECHNIQUE (PERT).  // Encyclopedia of Operations Research & Management Science;2001, p649 

    The article presents information on program evaluation and review technique. It is a method for planning and scheduling a project which models uncertainties in activity through the use of optimistic, likely and pessimistic time estimates for each activity.

  • Is Critical Chain Project Management Really a Novel Technique? Špundak, Mario; Fertalj, Krešimir; Kalpić, Damir // Central European Conference on Information & Intelligent Systems;2008, p48 

    In the growing discipline of Project Management (PM), the techniques used for project planning mainly include methods developed at dawn of modern PM back in 1950's. Therefore, they are influenced by Operational Research and are founded on Program Evaluation and Review Technique (PERT) or on...

  • EARLIEST FINISH TIME.  // Encyclopedia of Operations Research & Management Science;2001, p221 

    A definition of the term "earliest finish time" is presented. As described in a project network, it refers to the earliest possible time an activity can be completed without reducing the duration of any of the preceding activities. It is the sum of the duration of the earliest start time for the...

  • CHAPTER 6: Scheduling Project Work. Lewis, James P. // Fundamentals of Project Management;2007, p69 

    Chapter 6 of the book "Fundamentals of Project Management" is presented. It discusses the principles of scheduling within the context of project management. The use of Critical Path Method (CPM) and Program Evaluation and Review Technique (PERT) is demonstrated. Incorporating the concept of Work...

  • A new probabilistic approach to the path criticality in stochastic PERT. Monhor, Davaadorjin // Central European Journal of Operations Research;Dec2011, Vol. 19 Issue 4, p615 

    The notion of critical path is a key issue in the temporal analysis of project scheduling in deterministic setting. The very essence of the CPM consists in identifying the critical path, i.e., the longest path in a project network, because this path conveys information on how long it should take...

  • Ä°ÅŸ SÃœREÇLERÄ°NÄ°N MODELLENMESÄ°NDE GERT ÅŸEBEKELERÄ°NÄ°N KULLANIMI. Aytulun, S. Kerem; Ermis, Murat // Journal of Aeronautics & Space Technologies / Havacilik ve Uzay ;2010, Vol. 4 Issue 3, p19 

    Recent years, Firms have to use various and complex business processes for providing knowledge needs that is becoming increased. With understanding impact of the business processes on performance and profitableness of the firms, many academicians and managers need to get closer these business...

  • A STATISTICAL THEORY FOR PERT IN WHICH COMPLETION TIMES OF ACTIVITIES ARE INTER-DEPENDENT. Ringer, Larry J. // Management Science;Jul1971, Vol. 17 Issue 11, p717 

    This paper presents a method for taking into account dependency among certain activities in PERT networks. The method presented can be used with the reduction algorithm presented by Hartley and Wortham [1]. The addition of dependency among the completion times for certain types of activities...

  • ADVANCED NETWORK TECHNIQUES. O'Brien, James J. // SAM Advanced Management Journal (00360805);Fall69, Vol. 34 Issue 4, p77 

    Presents information on advanced techniques for management, such as the critical path method (CPM) and the program evaluation and review technique (PERT). Developers of CPM; Adoption of PERT by the aerospace industry; Information on some network variations.

Share

Other Topics