Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/11285
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDayal, Madhukar-
dc.contributor.TAC-ChairVerma, Sanjay-
dc.contributor.TAC-MemberRao, V. Venkata-
dc.contributor.TAC-MemberGhosh, Diptesh-
dc.date.accessioned2013-06-21T11:51:50Z-
dc.date.available2013-06-21T11:51:50Z-
dc.date.copyright2012-
dc.date.issued2012-
dc.identifier.urihttp://hdl.handle.net/11718/11285-
dc.description.abstractProject scheduling problem (PSP) has enticed researchers since over a century. Enhancement in computational power enables the search for solutions to more complex problems progressively. However, the search for optimal solutions to problems spanning a few thousand or more variables poses phenomenal challenges even today. A plethora of approaches – such as, exact solution approaches, heuristic, metaheuristic, and others – have been proposed and developed by researchers. Amongst the families of such optimization problems, the resource constrained project scheduling problems (RCPSP) represent one of the well-studied problems in literature, especially during and since the World War-II. A project consists of a set of activities partially ordered by precedence constraints. An activity has a given non-negative completion time, and can be performed in different modes. For each of its modes, the activity uses different types of resources, such as manpower, machinery, money etc., in either a different combination and/or different amounts. The resources considered are of, both, renewable and non-renewable nature. An activity is ready to be processed only when all its predecessor activities are completed and the numbers of units of the various resource types required by it, in the mode that it is to be performed, are free and can be allocated to it. Once started an activity is not interrupted and runs to its completion (non-preemptive). Scheduling is selecting the mode and committing resources to the realization of each activity at a defined time, while meeting the precedence and resource constraints. The aim is to assign modes and start times to activities so that the desired objective (makespan, flowtime, maximum tardiness, number of tardy jobs, etc.) is optimized. Several exact solution approaches to the single mode RCPSP have been presented in literature. However, only a few have considered the possibility of an activity being performed in more than one modes (Multi-Mode or MM). We study the MM-RCPSP for an exact solution, deploying breadth-first and best-first approaches with pruning rules while retaining the optimality of the solution. The algorithms perform better than the best existing exact algorithm by Sprecher and Drexl (1998) on standard test problem sets of the PSPLIB. We adopt our breadth-first approach for implementation on a computecluster with SMP (Shared Memory Processors) architecture. The implementation shows promising improvement in time taken to solve the PSPLIB problem instances with the increase in number of processors deployed to solve the problems.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesTH;2012/04-
dc.subjectProject scheduling problemen_US
dc.subjectscheduling problemen_US
dc.titleNew Exact Methods for Scheduling Multi Mode Multiple Resource Constrained Project Scheduling Problemsen_US
dc.typeThesisen_US
Appears in Collections:Thesis and Dissertations

Files in This Item:
File Description SizeFormat 
Madhukar.pdf
  Restricted Access
1.5 MBAdobe PDFView/Open Request a copy


Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.