Solving Resource-Constrained Project Scheduling Problem As .
Proceedings of the 10th WSEAS International Conference on COMPUTERS, Vouliagmeni, Athens, Greece, July 13-15, 2006 (pp80-86)Solving Resource-Constrained Project Scheduling Problem As aSequence of Multi-Knapsack ProblemsMILOŠ ŠEDAInstitute of Automation and Computer ScienceBrno University of TechnologyTechnická 2, 616 69 BrnoCZECH REPUBLICAbstract: - This paper describes a new technique for solving the duration minimization in a resourceconstrained network. It is based on a transformation of the resource-constrained project scheduling problem(RCPSP) to a sequence of (multi)knapsack problem (MKP) solutions. In the first part, three deterministicapproaches are summarized and their time complexity is discussed. Due to the combinatorial nature of theproblem for large projects with many constraints, heuristic techniques are applied. A genetic algorithmapproach is proposed and compared with simulated annealing.Key-Words: - multi-knapsack problem, resource-constrained scheduling, genetic algorithm, simulatedannealing1 IntroductionThe scheduling problem is a frequent task in thecontrol of various systems such as manufacturingprocesses [3], project management [7], and servicesystem control (reservation systems, timetabling).A classical task of project management is tocreate the network graph of a project and, on thebasis of knowledge or an estimation of time ofactivities, to determine critical activities that wouldhave influenced a project delay. Each activity drawson certain resources, e.g. financial resources, naturalresources (energy, water, material, etc.), labour,managerial skills. The solution of this task is wellknown in the case when we do not take limitedresources into consideration. There are manyprofessional programmes for the design of networkgraphs. Microsoft Project is one of the most userfriendly ones.However, in real situations, available capacitiesof resources are constrained to certain limits. Projectplanning under limited resources [3,7] is difficultbecause of interdependence among activities due to sharingthe same resources, dependence of resource consumption on themanner in which the activity is subdivided and dependence on the limits of availability of thevarious resourcesThe character of all the three dependencies isbasically non-linear. In general, schedulingproblems are NP-hard, consequently no polynomialtime algorithms are known to guarantee an optimalsolution.Classical methods of network analysis offersome approaches which depend on whetheractivities that have a lack of resource(s) may besuspended or not and whether activities will be putoff until the moment when it is possible to performthem. A question is: Which concurrent activitiesshould be suspended or put off because of a lack ofresource(s)?1.1 Related WorkAn excellent survey [5] with 203 references presentsclassification, models and methods for solving theresource-constrained project scheduling problem(RCPSP) and, in [10], it is critically reviewed andcompleted. There are single-mode and multi-modevariants of the problem, resources can be nonrenewable or renewable, activities of project can beinterrupted or not and so on.With respect to NP-hardness of the RCPSP,mainly heuristic methods are used for its solving.Papers frequently present applications of stochasticheuristics such as simulated annealing [4,16],genetic algorithms [2,11,12], tabu-search [1, 16, 19],ant systems [18] and swarm optimization method[22]. Most of these heuristics, applied to theclassical single-mode RCPSP minimising the
Proceedings of the 10th WSEAS International Conference on COMPUTERS, Vouliagmeni, Athens, Greece, July 13-15, 2006 (pp80-86)makespan of the project, are evaluated in acomputational study [14]. Multiobjective versions ofsimulated annealing and tabu search to the RCPSPto minimise the makespan, the weighted lateness ofactivities and violation of resource constraints aredescribed in [20]. Some authors combine more ofthese heuristics in hybrid procedures to improvetheir behaviour [12,18]. In [8], a special neighbourhood search method is presented where solutions arecoded by using activity sequences that are valid interms of precedence constraints.In spite of the fact that exhaustive search is outof the question for large instances of the problem, insome cases (and for smaller instances) exactmethods as backtracking and branch and boundmethod [9,21] may be used because they are able toreduce the search space substantially. In [6], analgorithm based on dynamic programming isproposed.among them. This strategy is of course not effectivebecause its time complexity is O(2n).3.2 Branch and Bound MethodFinding the solution may be faster using the branchand bound method [13], which restricts the growthof the search tree. Avoiding much enumerationdepends on the precise upper bounds (the lower theupper bounds, the faster the finding of the solutionis). Let items be numbered so thatvv1 v2 L nw1 w2wn(2)We place items in the knapsack by this nonincreasing sequence. Let x1, x2, , xp be fixedvalues of 0 or 1 and{}M k x x M , x j ξ j , ξ j {0,1}, j 1,K , p (3)where M is a set of feasible solutions. If2 Scheduling Via Knapsack ProblemsIf we consider a schedule as a sequence of timeintervals where neighbouring intervals based on thetime an activity starts or finishes, the schedulingproblem may be reduced to a set of the optimalchoices of activities in intervals. Using definedpriorities as prices, the task investigated in oneinterval corresponds to the well-known knapsackproblem. In the next paragraphs, we compare exactand heuristic approaches to solving this problem.( q )( p q n) :q 1 pj p 1w j C w jξ j j 1q j p 1w j (4)then the upper bound for Mk can be determined asfollows:pq 1j 1j p 1U B ( M k ) v jξ j vj pvq C w jξ j wq j 1 w j j p 1 q 1(5)3 Solving the 0-1 Knapsack ProblemAssuming only one resource with a limited capacity,we can deal with the 0-1 knapsack problem (0-1KP), which is defined as follows: A set of n items isavailable to be packed into a knapsack with capacityof C units. Item i has value vi and uses up to wi ofcapacity. We try to maximise the total value ofpacked items subject to capacity constraint.n n max vi xi wi xi C , xi {0,1}, i 1,K , n (1)i 1 i 1 Binary decision variables xi specify whether or notitem i is included in the knapsack.3.1 Combinatorial ApproachThe simplest way is to generate all possible choicesof items and to determine the optimal solution3.3 Dynamic ProgrammingLet us denote Fk(y) as maximal possible value usingonly first k items when capacity limit is y. Evidentlythe maximal value of a knapsack with capacity 0 is0, and maximal value of any knapsack is 0 if wehave no objects to put in it. That means:Fk (0) 0, 0 k nF0 ( y ) 0, 0 y C(6)(7)It may be shown that in general we get thefollowing recursive formulas: max{Fk 1 ( y ), Fk 1 ( y wk ) vk }, (8)Fk ( y ) if y wk 0; F ( y ),if y wk 0 k 1If we increase the capacity of the knapsack andthe set of objects that can be used to fill the sack,
Proceedings of the 10th WSEAS International Conference on COMPUTERS, Vouliagmeni, Athens, Greece, July 13-15, 2006 (pp80-86)and when y C and k n, then Fn (C) corresponds tothe maximum value of a knapsack with the fullcapacity, using all of the objects.A sequential evaluating of this formula uses twonested cycles:for k : 1 to n dofor y : 0 to C doevaluate Fk(y) and ik(y);The time complexity of this progression step isO(nC). It evidently depends considerably on thevalue of C.We have to trace choosing items during thecalculations. Denoting ik(y) as maximal index j itemused in Fk(y), we may show thati0 ( y ) 0, 0 y C(9) ik 1 ( y ), if y wk 0 Fk 1 ( y ) Fk 1 ( y wk ) vk ; ik ( y ) kif y wk 0 Fk 1 ( y ) Fk 1 ( y wk ) vk ; ik 1 ( y ), if y wk 0(10)Referring to the table of ik(y) values we have theanswer of which items to pack into a knapsack, inother words which activities will be performed in aninvestigated time interval and which activities willbe put off to the next interval.for i : 1 to n doxi : 0;{ Trace Back }i : in(C); k : n; y(i) : C;while i 0 dobegin if xi 0then begin xi : 1; y(i) : y(i) wi ;endelse k : k 1i : ik(y(i))end;Time complexity of the trace-back step is O(n).3.4 Heuristic MethodsThe three methods discussed above were exact(deterministic) methods. Now we will pay attentionto heuristic (stochastic) methods. These methods areused in situations where the exact methods wouldfail or calculations would require a great amount oftime.Heuristic [17] is a technique which seeks goal(i.e. near optimal) solutions at a reasonablecomputational cost without being able to guaranteeeither feasibility or optimality, or even in manycases, to state how close to optimality a particularfeasible solution is. The most popular heuristics –genetic algorithms, simulated annealing, tabu searchand neural networks are reviewed in [17]. Examplesof their possible use are described in [15].Let us briefly deal with the genetic algorithmsnow. The skeleton for GA is shown as follows:generate an initial population;evaluate fitness of individuals in the population;repeat select parents from the population;recombine parents to produce children;evaluate fitness of the children;replace some or all of the populationby the childrenuntil a satisfactory solution has been found;In the following paragraphs, we brieflysummarize GA settings to our scheduling problem.Individuals in the population (chromosomes) arerepresented as binary strings of length n, where avalue of 0 or 1 at the i-th bit (gene) implies that xi 0or 1 in the solution respectively.The population size N is usually chosen betweenn and 2n.An initial population consists of N feasiblesolutions and it is obtained by generating randomstrings of 0s and 1s in the following way: First, allbits in all strings are set to 0, and then, for each ofthe strings, randomly selected bits are set to 1 untilthe solutions (represented by strings) are feasible.The fitness function corresponds to the objectivefunction to be maximised:nf ( x) vi xi(11)i 1Pairs of chromosomes (parents) are selected forrecombination by the binary tournament selectionmethod, which selects a parent by randomlychoosing 2 individuals from the population andselecting the most fit one.The recombination is provided by the uniformcrossover operator. That means each gene in thechild solution is created by copying thecorresponding gene from one or the other parent,chosen according to a binary random numbergenerator. If a random number is 0, the gene iscopied from the first parent; if it is a 1, the gene iscopied from the second parent. After crossover, the
Proceedings of the 10th WSEAS International Conference on COMPUTERS, Vouliagmeni, Athens, Greece, July 13-15, 2006 (pp80-86)mutation operation is applied to each child. It worksby inverting each bit in the solution with a smallprobability. We use a mutation rate of 5/n as a lowerbound on the optimal mutation rate. It is equivalentto mutating five randomly chosen bits per string.If we perform crossover or mutation operationsas described above, then the generated children canviolate certain capacity constraints. We can assignpenalties to these children that prevent infeasibleindividuals from entering the population. A moreconstructive approach uses a repair operator thatmodifies the structure of an infeasible individual, sothat the solution becomes feasible. Its pseudo-Pascalcode is shown below for a more general case ofmultiple constraints. Once a new feasible childsolution has been generated, the child will replace arandomly chosen solution. We use a steady-statereplacement technique based on eliminating theindividual with the lowest fitness value. Since theoptimal solution values for most problems are notknown, the termination of a GA is usuallycontrolled by specifying a maximum number ofgenerations tmax. Usually we choose tmax 5000.3.5 Solving 0-1 KPEvidently the branch and bound method gives betterresults than the combinatorial approach, whose timecomplexity is O(2n), and it can be successfully usedfor n 100. Ratios vi/wi are sorted by Hoare'sQuickSort procedure. Its time complexity isO(n log2n).Since the dynamic programming procedure runsin O(nC) time, it seems to be quite good for solvingproblem instances when the capacity parameter Cand n are not too high. However, the use of thedynamic programming procedure approach is basedon the assumption that the capacity parameter C andweights wi are non-negative integers. Fractionalvalues may be converted to integers via multiplyingby the common denominator. On the other hand, ifall weights are integers, we may increment theparameter y in the progression step by the greatestcommon divisor. The drawback of the dynamicprogramming procedure is that, with growing n andC, memory requirements grow as well and forvalues higher than 1000, arrays for Fk(y) and ik(y)have more than millions of items, which causesproblems with memory managements or even, instatic representation of these arrays, thecorresponding programme cannot be compiled.4 Scheduling with MultipleConstraintsIn more complex and more frequent situations whenwe have more than one limited resource, wetransform the resource-constrained scheduling into asequence of multi-knapsack problem (MKP)solutions. MKP is defined as follows:nmaximise v i xii 1nsubject to wri xi Cr , r 1,K, m,(12)i 1xi {0,1}, i 1,K, nFor the solution of the task with multipleconstraints, we must generalise the approachesmentioned above.The combinatorial approach can be appliedwithout any changes, but using the branch andbound method, we must redefine the upper bound.For its evaluation we use the following formula{}U B ( M k ) min U 1B ( M k ), K , U Bm ( M k )(13)where auxiliary bounds U Bi ( M k ), i 1, K , mcorrespond to the given constraints and aredetermined as in the 0-1 knapsack problem. Beforeevaluation of these auxiliary bounds, the othervariables must be sorted again by decreasing valuesvj/wi j. Evidently, the run time will increasesubstantially.A generalisation of the dynamic programmingapproach is straightforward, but this approach isimpractical for its great number of enumerations andmemory requirements, e.g. we must evaluateFk ( y1 , K , ym ), 0 y1 C1 , K , 0 ym Cm ,(14)k 1, K , nAs noted above, in the GA approach, we use arepair operator to avoid infeasible solutions. Itspseudo-Pascal code shows the following algorithm.We assume that variables are sorted and renumberedaccording to the decreasing order of their pseudoutility ratios ui vi/wj i.J : {1, K , m}nW j : w ji xi , j J ;i 1for i : n downto 1 doif (xi 1) and (Wj Cj ; for any j J)then begin xi : 0;
Proceedings of the 10th WSEAS International Conference on COMPUTERS, Vouliagmeni, Athens, Greece, July 13-15, 2006 (pp80-86)Wj : Wj wji , j Jend;ak f al TS(0)( a ) δ (ak ) τ1Vkelse if TF ( ak ) TF (al )else if TF ( ak ) TF (al )then if R ( ak ) R ( al )5 Final ScheduleTo decide which of the concurrent activities are tobe suspended or put off because of a lack ofresource(s), we must define activity priorities. In thenetwork analysis literature, we may find manystrategies describing how the ranking of competingactivities is accomplished, for instance: greatest remaining resource demand, whichschedules as first those activities with thegreatest amount of work remaining to becompleted, least total float, which schedules as first thoseactivities possessing the least total float, shortest imminent activity, which schedules asfirst those activities requiring the least time tocomplete, greatest resource demand, which schedules asfirst those activities requiring the greatestquantity of resources from the outset.Our heuristic scheduling algorithm proposes thefollowing strategy. The time shifting of activities(when their total requirements are higher than theresource limit) is provided by prolonging theirduration. We distinguish for each activity a itsstarting duration ts(a) and current duration tc(a).Then δ(a) tc(a) ts(a) is a subintervalcorresponding to the shift activity during which ithas no requirements for resources. The greatestadvantage of this approach is that whenever we needto compute the new earliest and latest terms foractivities after shifts or updating the actual timeduration of certain activities, we may compute thewhole project by a simple CPM method. Precedencerelationships are kept and parameters of previousactivities do not change (in other words, any changein the present has no effect on the results in thepast).Let SV(a) denote the starting vertex of an activitya in the activity-on-arc representation of a networkgraph, a (i, j), Ti(0) denotes the earliest possibletime of realization of vertex i, TF(a) is the total floatof a and R(a) is the quantity of resources requiredby a. Investigating an interval [τ1, τ2], activities ak ,al from this interval are ordered by the followingrelation:(15)With this multilevel heuristic, we first try tocontinue activities that were begun in the previousinterval in order not to suspend the runningactivities. Then we review the least total float, andfinally look at the greatest resource demand. Priorityvalues are set proportionally to these criteria.5.1 ExperimentationThe approach discussed in the previous paragraphshas been implemented in Borland Delphi. Itsinterface is similar to Microsoft Project. AlthoughMicrosoft Project often is not able to solve aconstrained scheduling problem even for veryoversimple projects (it reports someallocation and underallocation maybe unavoidable), we have never come acrossthis situation when using our programme. Besidesthe GA approach, the programme implementsanother popular heuristic method - simulatedannealing - for a comparison, and a user maychoose between these two possibilities. It enables averification of the quality of computational results,as the exact results for large projects are not known.We have tested the proposed approach in manysituations. Table 1 shows results for one real projectwith 183 activities, 54 vertices in the network graphand 12 limited resources. This project deals with theinnovation action of a Benson boiler in a localpower station in the surroundings of Brno. Thistable contains durations of schedule for this projectdesigned in 30 tests by the genetic algorithm (GA)and by the simulated annealing (SA). Parameters forboth methods were set in a way such that thecomputational time for design of the projectschedule should be approximately 2.4 sec. Thebranch and bound (BB) method found a schedulewith a duration of 291 days in a several times longerCPU time. Favourable The results of BB achievedare favourable because the parallelism of activitieswas low. The dynamic programming approachcould not be used because of insufficient memory.While the results appear comparable,statistically, the results gained by GA are better thanthe SA results. The well-known Kruskal-Wallis testfor balanced one-way design was used to show that
Proceedings of the 10th WSEAS International Conference on COMPUTERS, Vouliagmeni, Athens, Greece, July 13-15, 2006 (pp80-86)samples were taken from the same population. It hasyielded the following results: Average rank forSA 39.75, for GA 21.25, the value of teststatistic 17.5472 and computed significance level 2.8 10 5. Thus the hypothesis of sampling from thesame population is rejected at all traditionally usedsignificance levels (0.05; 0.01; able 1. Durations for schedule (days) designed byGA and SA.6 ConclusionsIn the previous paragraphs, several approaches toconstrained scheduling were discussed.
problem for large projects with many constraints, heuristic techniques are applied. A genetic algorithm approach is proposed and compared with simulated annealing. Key-Words: - multi-knapsack problem, resource-constrained scheduling, genetic algorithm, simulated annealing 1 Introduction The scheduling problem is a frequent task in the
decades types of project scheduling planning techniques under resource constrained conditions were proposed, implemented and controlled which generally are divided to exact and approximate methods. In fact it can be told that resource-constrained project scheduling problem has more than 40 years history.
disappointing, that project teams that have put in the significant effort and cost to create a resource-constrained model could reap huge time and cost savings simply by running there already built model through a different scheduling engine. Figure 1 illustrates the potential impact of different scheduling algorithms in a resource-constrained .
Resource Algorithms Resource Leveling Moving activities within float to minimize fluctuations No change to schedule duration! Especially important for human resources No guarantee that falls within limits of available resources! Resource Scheduling ("Constrained-resource scheduling", "Limited Resource Allocation") Scheduling resources within constraints with minimal extension
Different packages create different resource constrained schedules for the same project. Therefore project planners must not blindly rely on the schedules offered by their tools and must look into these schedules for possible improvements. 24 Resource Constrained Scheduling
Calhoun: The NPS Institutional Archive Theses and Dissertations Thesis Collection 1996 An evaluation of the time constrained and resource constrained scheduling features of commercially
did not cover this situation. Hence, the resource-constrained multiproject scheduling consideration is es-sential[34]. 2.3. Resource-Constrained Multiproject Scheduling. Typically, multiple projects share common resource pools whose capacities are not sufficient to support all project activities at the same time, leading to the resource-
Production scheduling methods can be further classified as static scheduling and dynamic scheduling. Static operation scheduling is performed during the compilation of the application. Once an acceptable scheduling solution is found, it is deployed as part of the application image. In dynamic scheduling, a dedicated system component makes
2020 Manual for Railway Engineering (MRE) – Individual/Downloadable Chapters in PDF format. Visit www.arema.org Publication Title Member Price Non-Member Price S & H Fee Schedule Quantity Total Cost 2020 Manual for Railway Engineering (MRE) – Annual Publication released every April Complete Print Set 960 1,470 1
