Availability and Conditions of Agricultural Machinery in Public and Private Sectors of Borno State, Nigeria Arid Zone Journal of Engineering, Technology and Environment. October, 2007; Vol.5, 85-93 Copyright© Faculty of Engineering, University of Maiduguri, Nigeria. Print ISSN: 1596-2644, Electronic ISSN: 2545-5818 www.azojete.com.ng FORMULATION OF CONSTRUCTION PROJECTS AS SINGLE-MODE RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEMS (SMRCPSP) Adamu P1, O. Abass2 and R. Okafor 3 Abstract The paper presents the resource–constrained project-scheduling problem with the single execution mode for each activity and makespan (project’s completion time) minimization as objective. Several heuristic procedures for solving the problem have been proposed in the literature including a decomposition-based genetic algorithm and maximizing the net present value of projects. The formulation of construction projects as SMRCPSP using the bill of quantities, material schedule and the program of the construction projects, using a building construction project is presented. Applying any of the good existing algorithms for solving this class of problems, will enable civil engineers to determine how to schedule the jobs in a construction project for execution so that completion times are minimized even if resources are insufficient? This will help to reduce the rate at which individuals or construction companies abandon their projects half way to completion times. It is a viable way to manage resource crises in construction companies. 1. Introduction Project scheduling is distinguished from job shop and other related types of scheduling by the non-repetitive nature of the work. A project is usually thought of as a one-time effort, although, this may not always be the case. Similar efforts may have been undertaken previously, but not on a production basis. For example, the construction of a building, a highway, or a ship might be thought of as typical projects. In addition, periodic maintenance operations, administration of research and development programs, installation of a new computer facility, and the development and implementation of a new management information system are also activities that can be treated by project scheduling methods. A project consists of a set of activities or jobs, which must be accomplished for the project to be completed. The essential components of a project are usually the degree of non-repetitiveness, the time frame and the magnitude of costs involved. The planning and control of large projects is a difficult and important problem of modern enterprise that many network planning techniques have tried to handle. However, practical application of these techniques leads, to many difficulties. During the planning phase of a project, project management must solve a lot of technical problems as well as those involving time, cost and resource aspects. Common network planning techniques, such as Metra Potential Method (MPM) and Critical Path Method (CPM) essentially concern themselves with the time aspect only. These methods aim to minimize project duration, assuming that the various resources required for project completions are available. In practice however, project completion requires the use of various resources, whose often- limited availability directly influences planning objectives, time 1 Mathematics Department, University of Maiduguri, Maiduguri. Nigeria 2 Computer Science Department, University of Lagos, Akoka, Lagos. Nigeria 3 Mathematics Department, University of Lagos, Akoka, Lagos. Nigeria http://www.azojete.com.ng/ Formulation of construction projects as single-mode resource-constrained project scheduling problems 86 estimations and, scheduling and progress control. When activities require resources for their execution, (e.g. manpower, materials, equipment, capital etc.) that are only available in a limited amount, bottle-necks may appear, e.g. activities cannot be started on time due to the unavailability of resources or activities requiring the same resource which is only available, one unit at the time must be delayed, etc. The various resource problems that may appear during project scheduling can be divided into three classes: time/cost trade-off, resource leveling and resource allocation (Herroellen, W.S. 1972). Time/cost trade-off problems: This problem may appear when there are no constraints on the availability of resources. The problem then consists of reducing project completion time by adding additional resources to certain activities, so that the execution of these activities may be accelerated. When this is the case, there are many different ways in which activity duration may be selected so that project completion times of the resulting schedules are all equal. However, each schedule may yield a different value of total project direct cost. It would therefore be desirable to have some method for determining the least costly schedule for any given project duration. Several such methods have been developed each of which hinges upon various assumptions about the form of the activity direct cost-relationship. This class of problems has been extensively reviewed by Kolisch and Padman (1997) and is outside the scope of this research. Resource-leveling problems: This problem occurs when sufficient resources are available for the completion of the project. The objective may be, given a total project completion time, to level the various resource requirements over time. (i.e. to keep the resource usage as much as possible to a constant rate).This problem for which many optimization and heuristic procedure are available ((Zimmermann, 1997), (Brinkmann and Newmann, 1996), (Newmann and Zimmermann, 1998), etc.) also, lies outside the scope of this research. Resource allocation or resource-constrained problems: This problem arises when there are limited amounts of the resources required by the activities of the project. Because the amounts available are not always sufficient to satisfy the demands of concurrent activities, sequencing decisions are required, with a resultant increase in project duration beyond that determined by the “Critical Path” (the resource non-constrained duration). The objective is to make the required sequencing decisions in such a fashion, that the increase in project duration is minimized, subject to the given resource and precedence constraints. It is this type of problem that forms the subject of this research. 2. Description of the SMRCPSP The Single-Mode Resource-Constrained Project Scheduling Problem (SMRCPSP) is the scheduling problem where each of the activities of the project has to be performed in one prescribed way (mode) using specified amounts of the resources provided. The objective of the SMRCPSP is the minimization of makespan. Examples are Baar, et al. (1998), Brucker, et al. (1998), Kolisch, and Sprecher (1997)and Drexl, et al. (1999). In order to model the single-mode resource-constrained project scheduling problem (SMRCPSP), the following is considered: A single project consists of j = 1,…, J activities AZOJETE Vol. 5 2007 87 with a non-preemptable duration of dj periods. The activities are interrelated by precedence and resource constraints: Precedence constraint forces an activity not to be started before all its predecessors are finished. Pj defines the set of immediate predecessors of activity j. For ease of notation the activities are topologically ordered, i.e., each predecessor of activity j has a smaller number than j. Furthermore, activity j = 1 is defined to be the unique dummy source while activity j = J is defined to be the unique dummy sink. Resource Constraints arise as follows: In order to be processed, activity j requires kjr units of resource type r  R during every period of its duration. Since resource r is only available with the constant period availability of Kr units for each period, activities might not be scheduled at their earliest (precedence-feasible) start time but later. Our objective is to schedule the activities such that precedence and resource constraints are obeyed and the makespan of the project is minimized. T denote an upper bound on the project’s makespan. Then we obtain a time-window [EFTj, LFTj] of earliest and latest finish times for the completion time of each activity j by performing a forward recursion and a backward recursion with LFTj = T as e.g., outlined in Elmaghraby (1977). Defining the decision variables 1, if activity j is finished precisely at the end of period t xjt = 0, otherwise as proposed by Pritsker et al.[1969], the following 0-1 programming model for the SMRCPSP arises (Patterson and Huber,1974; Patterson and Roth,1976): Table 1: The model of SMRCPSP LFJ Minimize φ = ∑ t . xJt (1) t=EFJ subject to LFj ∑ xjt = 1, j = 1, …, J (2) t=EFj LFi LFj ∑ t xit < ∑ (t – dj) xjt j = 2,…, J, i є Pj (3) t =EFj t =EFj J t+dj-1 ∑ kjr ∑ xjr < Kr r є R, t = 1,…, T (4) j =1 r = t xjt є {0, 1} j = 1,…,J, t = EFj,…, LFj; (5) Formulation of construction projects as single-mode resource-constrained project scheduling problems 88 The objective function (1) minimises the completion time of the unique sink and thus the makespan of the project. Constraint set (2) assures that to each activity a unique finish time, within its time window is assigned. Constraint (3) take into consideration the precedence relations between each pair of activities (i, j), where i immediately proceeds j. finally, constraint set (4) limits the total resource usage within each period to the available amount. Since the SMRCPSP is a generalisation of the static job shop problem it belongs to the class of NP-hard problems (Blazewicz et al., 1983). Consequently, only heuristic solutions can be derived when facing large real-world problems (Kolisch and Drexl, 1996). The purpose of this paper is to formulate the resource problems faced by individuals or construction companies when building houses, bridges, roads, etc, as SMRCPSP. When any of the good existing algorithms for solving this class of problems is applied to the resource– constrained problem, the result will help the engineers to determine how to schedule the jobs in a project for execution, so that completion times are minimized even if resources are insufficient. This may help to reduce the rate at which individuals or construction companies abandon their construction projects before completion times. 3. Formulation of SMRCPSP from an activity listing of a bungalow The construction of buildings, roads, railways, bridges, etc can be formulated as SMRCPSP using the bill of quantities, material schedule and the program of the construction projects. This is done by considering one activity at a time: 1) finding out the durations of each activity, 2) and finding out the combining level of resource requirements with the related duration. For example, Table 2 is an activity list of a bungalow. AZOJETE Vol. 5 2007 89 Table 2: A bungalow activity listing Activity No. Description Previous activities Duration /day Resources required/men skilled laborers cost/$100 1 Obtain joinery - 60 0 0 5 2 Obtain glass - 20 0 0 3 3 Obtain Sanitary ware - 20 0 0 2 4 Obtain heating equipment - 40 0 0 2 5 Obtain electrical equipment - 30 0 0 2 6 Obtain plumbing equipment - 70 0 0 1 7 Obtain tiles - 140 0 0 4 8 Obtain bricks - 60 0 0 6 9 Obtain top-soil - 40 0 0 2 10 Survey the site - 20 2 5 1 11 Build temporary access 10 30 2 5 5 12 Earthworks 11 10 2 5 5 13 Lay foundations 12 30 2 5 5 14 Install external drainage 6;13 20 2 3 6 15 Build Shell (outer structure) 13 80 2 9 1 16 Build boiler-house 4;15 20 2 6 6 17 Place electrical wiring 5;15 40 2 1 5 18 Install interior plumbing 14;15 50 2 3 7 19 Fix roof frames 15 20 5 10 1 20 Build interior walls 8;19 50 2 5 6 21 Place roofing 7;19 20 3 6 7 22 Build outside storage and garage 15 20 4 3 4 23 Install wood fames 1;18;20;21 40 2 5 4 24 Install sanitary ware 3; 18; 21 30 1 2 8 25 Install boiler 16; 21 10 3 7 2 26 Inspect wiring 17 10 0 0 1 27 Lay permanent access 21 30 1 2 2 28 Fit glass 2; 23 20 2 8 7 29 Install switches and plugs 21; 26 10 2 1 4 30 Finish exterior 22; 27 50 1 3 6 31 Surface walls and partitions 28 30 2 4 6 32 Connect plumbing and test 24; 29 10 2 5 7 33 Clean up outside 30 10 1 4 3 34 Finish interior 31; 32 30 2 5 5 35 Place flagstones 9; 31; 32 30 2 5 3 36 Place top-soil, and landscape 35 20 2 5 2 37 Overall inspection 33; 34; 36 10 2 5 4 38 Project complete 37 0 0 0 0 Resource Available each period (kρ it) 6 11 9 Formulation of construction projects as single-mode resource-constrained project scheduling problems 90 Figure 1 is the network of the above activity list of the bungalow. Figure 1: Network diagram of the building project AZOJETE Vol. 5 2007 91 Using the bill of quantities, the material schedule and the program of the bungalow in Table 2, below is the formulated SMRCPSP. Table 3: precedence relations Jobnr. #modes #successors successors 1 1 1 23 2 1 1 28 3 1 1 24 4 1 1 16 5 1 1 17 6 1 1 14 7 1 1 21 8 1 1 20 9 1 1 36 10 1 1 11 11 1 1 12 12 1 1 13 13 1 2 14 15 14 1 1 18 15 1 5 16 17 18 19 22 16 1 1 25 17 1 1 26 18 1 1 29 19 1 2 20 21 20 1 1 23 21 1 4 23 24 27 30 22 1 1 31 23 1 1 25 24 1 1 33 25 1 1 29 26 1 1 29 27 1 1 30 28 1 1 31 29 1 1 32 30 1 1 33 31 1 2 34 35 32 1 1 34 33 1 1 37 34 1 1 37 35 1 1 36 36 1 1 37 37 1 1 38 38 1 0 0 Formulation of construction projects as single-mode resource-constrained project scheduling problems 92 Table 4: request / duration jobnr. mode duration R1 R2 R3 ------------------------------------------------ 1 1 60 0 0 5 2 1 20 0 0 3 3 1 20 0 0 2 4 1 40 0 0 2 5 1 30 0 0 2 6 1 70 0 0 1 7 1 140 0 0 4 8 1 60 0 0 6 9 1 40 0 0 2 10 1 20 2 5 1 11 1 30 2 5 5 12 1 10 2 5 5 13 1 30 2 5 5 14 1 20 2 5 6 15 1 80 2 9 1 16 1 20 2 6 6 17 1 40 2 1 5 18 1 50 2 3 7 19 1 20 5 10 1 20 1 50 2 5 6 21 1 20 3 6 7 22 1 20 4 3 4 23 1 40 2 5 4 24 1 30 1 2 8 25 1 10 3 7 2 26 1 10 0 0 1 27 1 30 1 2 2 28 1 20 2 8 7 29 1 10 2 1 4 30 1 50 1 5 6 31 1 30 2 4 6 32 1 10 2 5 7 33 1 10 1 4 3 34 1 30 2 5 5 35 1 30 2 5 3 36 1 20 2 5 2 37 1 10 2 5 4 38 1 0 0 0 0 ************************************************* RESOURCE AVAILABILITIES: R1 R2 N1 6 11 9 AZOJETE Vol. 5 2007 93 4. Conclusion In this paper is the formulation of an activity list of a bungalow as a SMRCPSP using the bill of quantities, the material schedule and the program of the bungalow. Other construction projects, like the construction of roads and bridges can be formulated as presented in this paper. When any of the good existing algorithms for solving this class of problems is applied to the resource–constrained problem, the result will help the engineers to determine how to schedule the jobs in a project for execution so that completion times are minimized even if resources are insufficient. This will help to reduce the rate at which individuals or construction companies abandon their projects before completion times. It is one of the ways to manage resource crises in construction companies. References Drexl, A and J. Grunewald (1993). Nonpreemptive Multi-Mode Resource-Constraint Project Scheduling. IIE Transactions, 25(5): 74-81, Elmaghraby, S.E. (1977). Activity Networks: Project planning and Control by Network Models. Wiley, New York,. Fleszar K. and K. Hindi (2004). Solving the Resource-Constrained Project Scheduling Problem by a Variable Neighbourhood Search, European Journal of operations Research, 155(2):402-413. Garey, M.R. and D.S. Johnson (1977). Computers and Intractability; A Guide to the Theory of NP-Completeness. Freeman, San Francisco, C.A. Hartmann, S. and A. Drexl (1998). Project scheduling with Multiple Modes: A Comparison of Exact Algorithms. Technical Report 430, Manuskripe aus deb instituten fur betriebwirtschaftslehre der Universitat Kiel. Herroelen W.S. and Leus (2004). The construction of stable project baseline schedules. European Journal of Operations Research. 156(3) 550-565. Kolisch, R. and A. Drexl (1997). Local Search for Nonpreemptive Multi-Mode Resource- Constrained Project Scheduling. IIE Transactions, (29): 987-999. Kolisch, R. (1995). Project-Scheduling under Resource-constraints: Efficient heuristics for several problem classes. Physica-Verlag, Hiedelberg. Slowinski, R. (1980). Two approaches to problem of resource allocation among project activities: A Comparative Study. Journal of the Operational Research Society. (31): 711-723. Sprecher, A. and A. Drexl (1996). Solving Multi-Mode Resource-Constrained Project Scheduling Problems by a Simple General and Powerful Sequencing Algorithm. Part I: Theory. Technical Report 385, Manuskripe aus deb instituten fur betriebwirtschaftslehre der Universitat Kiel. Sprecher, A. (1996). Solving the RCPSP Efficiently at Modest Memory Requirements. Technical report 425, Manuskripe aus deb instituten fur betriebwirtschaftslehre der Universitat Kiel. Talbot, F.B and J.H. Patterson (1978). An Efficient Integer-Programming Algorithm with Network Cuts For Solving Resource-Constrained Scheduling Problems. Management Science, 24(11):1163-1174. Weglarz, J. (1980). On certain models of resource allocation problems, Cybernetics, (9) 61-66.