Đang chuẩn bị liên kết để tải về tài liệu:
Heuristic algorithm for single resource constrained project scheduling problem based on the dynamic programming

We introduce a heuristic method for the single resource constrained project scheduling problem, based on the dynamic programming solution of the knapsack problem. This method schedules projects with one type of resources, in the non-preemptive case: once started an activity is not interrupted and runs to completion. | Yugoslav Journal of Operations Research Volume 19 (2009) Number 2, 281-298 DOI:10.2298/YUJOR0902281S HEURISTIC ALGORITHM FOR SINGLE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM BASED ON THE DYNAMIC PROGRAMMING Ivan STANIMIROVIĆ1, Marko PETKOVIĆ2 Predrag STANIMIROVIĆ3* and Miroslav ĆIRIĆ4 1,2,3,4 University of Niš, Department of Mathematics and informatics, Faculty of Sciences and Mathematics, 1 ivan.stanimirovic@gmail.com, 2dexterofnis@neobee.net, 3 pecko@pmf.pmf.ni.ac.rs, 4ciricm@bankerinter.net Received: May 2006 / Accepted: October 2009 Abstract: We introduce a heuristic method for the single resource constrained project scheduling problem, based on the dynamic programming solution of the knapsack problem. This method schedules projects with one type of resources, in the non-preemptive case: once started an activity is not interrupted and runs to completion. We compare the implementation of this method with well-known heuristic scheduling method, called Minimum Slack First (known also as Gray-Kidd algorithm), as well as with Microsoft Project. Keywords: Resource scheduling, dynamic programming, knapsack problem, DELPHI. 1. INTRODUCTION In practice most organizations work within limited resources, so projects are subject to the same constraint. A new project may seek an additional use of resources, so it is needed to ensure that they really would be available. * Corresponding author 282 I. Stanimirović, M. Petković, P. Stanimirović, M. Ćirić / Heuristic algorithm On the other hand, the time constraints are always present, so project manager must work under that boundary. Resource leveling is a way to resolve having too much work assigned to resources, known as resource over allocation. The network diagram can be used to find opportunities for shortening the project schedule. This involves looking at where we can cut the amount of time it takes to complete activities on the critical path, for example, by increasing the resources available to .