Kaynak kısıtlı proje programlama problemlerinin çözümü için yeni yöntem ve algoritmalar

Abstract

ÖZET Proje Planlama çağdaş anlamda CPM, PERT ve MPM yöntemlerinin yaklaşık 30 yıl önce geliştirilmesiyle doğ muştur. Analiz ve sentez aşamalarında belirlenen işlem lerle, projelerin şebeke ya da ağ diyagramı adı verilen grafik modellere dönüştürülüp programlanmasını sağlayan bu `Kritik Yol Analizi` yöntemlerinde `kaynak` ve `mali yet` unsurlarının gözardı edilmesi, ilginin `kısıtlı kay naklarla programlama problemleri üzerinde toplanmasına yol açmıştır. `Kaynak Kısıtlı Proje Programlama` adı ve rilen kombinatorik karakterli bu problem 1. ve 2. Bölüm lerde incelenmektedir. Bu çalışmada problemin şu yönleri vurgulanmıştır: - İşlemler, kaynak ikamesi yapılarak, farklı süre ve maliyet yaratan teknoloji seçenekleriyle gerçekleşti rilebilir. - Fiziki kaynakların kapasiteleri yanında, bu kay nakların kullanım maliyetlerini karşılayan nakit akışı da kısıtlıdır. - Her işlemin başlama zamanıyla, uygulanacak tek noloji seçeneğinin bağıntı, kaynak ve nakit akış kısıt ları altında altında belirlenmesiyle çözüme ulaştırılan problem, sonlu sayıda çözüm içeren çok aşamalı bir karar problemi niteliği taşımaktadır. 3. Bölümdeki literatür taraması, yapılmış olan ça lışmaların daha çok teknoloji seçenekleri ve nakit akışı kısıtlarına yer vermeyen klasik problemler üzerinde yo ğunlaşmış olduğunu ve bu problemlerde bile, optimizasyon yöntemlerinin genel olarak yetersiz, sezgisel yöntemle rin' güvenilirlikten yoksun olduğunu ortaya koymuştur. Bu çalışmada geliştirilen çözüm yöntemleri şu il kelere dayandırılmıştır: - Probabilistik öğeler içeren yöntemlerle, proble min çözüm uzayında yöresel taramalar yapılarak bir sezgi sel yöntemle sağlanan çözümden daha iyi çözümler ve çe şitli çözüm seçenekleri oluşturulabilir. - Probabilistik çözüm süreci, altçözüm oluşturma, değerlendirme ve eleme ölçütleri içeren `karar ağacı` yaklaşımıyla etkinleştirilebilir. Bu ilkelere göre geliştirilen ve 4. Bölümde açıkla nan yeni yöntemler benzetimle oluşturulan problemlerde uygulanmış, klasik öncelik kuralı ve probabilistik yöntem lerle karşılaştırılmıştır. 5. Bölümdeki istatistiksel de ğerlendirmeler, projelerde kesitler oluşturularak aşamalı programlama ilkesine dayanan probabilistik yöntemlerle çözüm etkinliğinin bariz şekilde arttığını göstermiştir. - xiii -

SUMMARY NEW METHODS AND ALGORITHMS FOR SOLVING THE RESOURCE - CONSTRAINED PROJECT SCHEDULING PROBLEM The development of the Critical Path Methods CPM, PERT and MPM in the mid 1950' s gave a strong impuls to the efforts of creating effective techniques for scheduling and managing projects. Although, ways of calculating `activity times and floats` are clearly described with these basic methods, other main features like `resources` and `costs` are not taken into consideration. The problem of scheduling a project becomes very complex, specially when scarce resources and costs axe taken explicitly into account. The so called `Resource- Contraint Project Scheduling` (RCPS) problem belongs to a class of combinatorial problems that is not satisfactorily solved yet. The process of scheduling a project under resource constraints can be characterized as a multi-stage decision, making problem. At each stage, there exists a number of activities that can be started without violating precedence constraints, but since resources are limited not all of them can be assigned a resource feasible starting time. To decide, which activity will be scheduled first and which ones have to be delayed shows that two sub-problems arise at each stage: Sequencing activities according to some criteria and choosing activities to schedule from the ordered set according to some rules or methods. This problem has a finite number of feasible solutions, because with each different decision about sequencing and choosing activities to schedule, a different schedule is obtained. Each schedule can be evaluated according to some objective functions or criteria. Hence, a procedure to solve the problem of RCPS is mainly a method of calculating feasible solutions of the problem in order to find out the best one (in optimization approaches) or a good one (in heuristic approaches). Shortly, the aim of this study can be stated as follows : Considering a category of RCPS problems, in which activity durations and costs are assumed to be discrete functions of resources assigned to them, it's aimed to develop new and effective probabilistic sampling procedures which involve aspects of decision tree approachs like evaluation bounding and pruning of - xiv -partial schedules in the sampling process. In order to evaluate the effectiveness of the developed procedures, an experimental investigation has been carried out. 80 test problems have been simulated. On each problem, new and standard probabilistic sampling procedures and methods of producing solution alternatives with a number of different priority rules are applied. The performances of all methods are evaluated statis tically with respect to solution quality and solution times. The analysis of variation followed by the studentized t-range test showed that with the sampling procedure involving a mechanism of producing cuts at definite stages of the sampling process and evaluation of partial schedules the solution quality can be increased considerably without changing solution times drastically. This dissertation has 5 chapters. First two of them are devoted to the main problems of project planning and scheduling. In the third chapter, methods for solving RCPS problems are surveyed. In the last two chapters, the sampling procedures, the project model and experimental work are explained. In the first chapter, a brief outline of the process of planning and controlling projects is given. At the stages of project analysis and synthesis the data for the scheduling problem are determined. Analysing a project involves mainly the tasks of defining and planning the activities which have to be performed in order to realize the aim of the project. In this sense, an activity is defined as a time consuming structural element of a project, realized by using definite amounts of renewable resources as machines, man power etc. and by purchasing definite amounts of non-renewable resources like money, material, energy etc. As stated above, resources are classified into two categories. The attribute `renewable` indicates that by resources which create a capacity on each time unit the usage is restricted by the amount of the units availible. `Non-renewability` shows that the total consumable amount of a resource (e.g. money) over a period of time is limited. With `resource` we'll implicitly assume renewable resources and non-renewable resources will be stated explicitly or `cash flow` will be used to state the amounts of non-renewable resource `money` assigned to the project. Capacity of a resource is simply defined as the usage duration of a unit resource per time unit (e.g. hours/day or shifts /week) during which it operates under `normal working conditions` determined by project management. This `normal` capacity can be forced and inreased by over-time working (time adjustment) or by increasing the productivity, motivating the personnel or raising the speed of machines beyond the optimal (productivity adjustment). - xv -In project analysis, the relationships between resources, costs and duration of activities are established. The interchangability of some resources shows that there may be a set of technological alter natives to perform an activity, e.g. a job of turning a number of machine spindles can be performed by using universal lathes and skilled labor or with NC- lathes and a technician. With each alternative, activity duration and cost are functions of the amount of resources assigned to the activity and of the capacity of the resources when adjusted by forcing. With these definitions, it's explicitly assumed that activity duration is a variable and to fix it a feasible combination of resource types, their amounts and capacities for a choosen technological alternative have to be determined. Project synthesis is concerned with establishing precedence relationships between activities and to create a grafic model of the project, generally called `project network`. Derived from a general network model, there are 3 kinds of networks of which the first two are widely used: Activity-O.n-Node (or precedence) diagrams, Activity On- Arrow networks and Event-On-Node networks (original PERT- Networks). As stated in the second chapter, the problem of project scheduling has the following form: - Decision variables: A solution to the problem is gained, if for each activity a definite `starting time`, the `technological alternative` to perform the activity (the combination of resource types) and the `amount and capacity of assigned resources` are determined. Each different set of values for these variables results in a different schedule. - Constraints: Three main constraints of the problem are `precedence constraints`, `resource con strains` and `time constraints`, if for some of the activities time limits are set or if project completion is fixed in time. - Objectives: Generally, the main objective of project scheduling is `minimization of the total project cost`. Project costs are influenced by three variables: Project duration, activitiy durations and capacity loading. Direct costs of activities can be expressed as functions of activity durations and total direct cost as a function of project duration. For a given project duration, a schedule which causes a minimum total of direct costs can be obtained. Similarly, indirect costs of a project, tardiness penalties and opportunity costs are also functions of project duration. Fluctuations in capacity loading are the main cause of a set of costs (e.g. hiring or dismissal costs) which can not be easily expressed as a function of project duration. In general, the total project cost curve, obtained as sum of direct and indirect costs of a project does not include costs - xvi -affected by fluctuations in capacity loading. The complexity of the project scheduling problem in its general form has led researchers to simplify, the problem by making some assumptions concerning decision variables, constraints and objectives. In the historical course of research, 4 main problems with increasing complexity were subject of many studies: `Critical Path Analysis`, `Time-Cost Trade-Off`, `Resource Levelling` and `Resource Constrained Project Scheduling` (RCPS). Since resource constraints are not taken into consider ation in the first three problems, it can not be asserted that realistic and applicable schedules could be obtained by solving these problems. Hence, the only viable way of getting realistic solutions of the problem is RCPS. RCPS models are classified in two main groups: In classical RCPS models (RCPS1), its assumed that; activity durations, resource requirements and direct costs are fixed at the project analysis stage. The problem consists of `assigning resource and precedence feasible starting times to activities`. Since direct costs are fixed, the objective can be defined as `minimizing the project duration` which is equivalent to minimizing the duration dependable indirect costs. In RCPS2 models, activity durations are assumed to be discrete or continious functions of the resources assigned to them. RCPS2, also called `Time-Resource Trade-Off` is a class of more complex scheduling problems in which time, resource and cost aspects are considered explicitly. RCPS models can further be classified into single- and multi-project, single- and multiple-resource models. Considering activity splitting, one can also distinguish between preemptive and non-preemptive models, and another differentiation can be made by assuming that the resource requirements are fixed over the activity duration or not. In this study, a single-project, multiple-resource non-preemptive RCPS2 problem is considered in which resource requirements are assumed to be fixed over activity duration. As described in the fourth chapter, main features of the model can be summarized as follows: For each activity a set of technological alter natives are defined. With each alternative the types and amounts of resources, their capacities and so the activity duration is fixed, i.e. activity durations are assumed to be discrete functions of resources assigned. Also, each alternative creates a different direct activity cost. Resources are limited in each time period over the project duration. To account for costs of using resources by performing activities non-renawable resource, `money` is assigned to the project in definite amounts and on definite time points during project realization. This assignment shows that there is a `cash flow` to the project which is a function of time. To perform any - xvii - 7activity of the project with one of the technological alternatives in a definite time period, renewable resources and cash flow have to satisfy the requirements of the activity. The project is represented with an activity-on- node diagram in which only finish-to-start relations be tween activities are considered. The decision variables are resource, cash flow and precedence feasible `starting times` and `technological alternatives` (resource-duration combinations) of activities. Feasible solutions of the problem can be evaluated with respect to several objective functions: Minimizing the project duration, minimizing the direct costs of activities or minimizing the sum of direct costs and duration dependent indirect costs of projects. In the third chapter, the existing solution procedures to the RCPS problem are classified and surveyed. In early attempts, the RCPS1 problem has been formulated as integer LP (mostly as 0-1 LP) models, but standart procedures for these models have generally failed to give exact (optimal) solutions for problems of real-life size. With numerious enumerative procedures such as branch-and-bound, bounded enumeration and others, effectiveness of producing optimal solutions in reasonable computing times have been increased, but yet the overall efficiency of the optimization procedures is not promising. The same applies also for RCPS2 problems, for which very few attempts have been made to solve them exactly. In general, the combinatorial nature of the RCPS problem shows that exact solutions can not be obtained for real life problems and even with powerfull computers, RCPS1 problems with at most 100 activities and 5 resource types can be solved in acceptable computing times. On the other hand, the main disadvantage of `heuristic procedures` is that they are highly unreliable in assuring the solution quality. Numerious investig ations have been carried out, but all of them concluded that neither a `priority rule` applied in sequencing the schedulable activities nor the elaborate `near optimal solution procedures` could always give equally good results on all problems. Most of this research has been carried out on RCPS1 problems. To search for better heuristic solutions several approaches have been suggested which mainly involve methods of calculating a number of solution alternatives in order to select an appropriate one: 1- By applying different `priority rules` iterati- vely on the same problem a number of schedule alter natives can be obtained. With this approach, the un certainly about the effectiveness of priority rules when used in a single trial can be avoided. 2- Heuristic decision tree approachs can be devel oped with which the calculation of partial schedules, - xviii -bounding, pruning and branching are carried out according to some heuristic criteria and rules, such as max. number of partial schedules evaluated at each stage, max. number of branches obtained from a nodeetc. 3- Random sampling is another way of producing a specified number of solution alternatives. With this method, at each stage of the solution process activities for scheduling are selected randomly. In a set of schedulable activities, the probability of each activity being selected first is equal. 4- In probabilistic sampling, also called `biased random sampling`, aspects of priority rule based procedures and random sampling are combined. At each stage, schedulable activities are ordered according to a priority criterion and weighted probabilities are assigned to each activity of the ordered set. Selection of activities is then made randomly, considering weighted probabilities. For the determination of weighted probabilities several methods can be applied. In this study, they are calculated by using truncated geometrical distribution. The properties of this distribution are such that, the probabilities can be biased with a parameter Q which determines nearly the weighted probability of the first activity in the ordered set. For higher values of Q nearing 1, the weight of the `priority rule` in schedul ing is increased since the probability of the first activity in the ordered set increases. For lower values, randomizing effects get stronger. In this study six algorithms are developed. Three of them are based on the above stated first, third and fourth approaches, named respectively ÇÖK, RAS and ARP1 algorithms. Combining main aspects of the second and forth approaches three new procedures, coded as ARP2, ARP3 and ARP4 are introduced. Main features of the new algorithms can be summarized as follows: The sampling process can simply be viewed as an application of a schedule generation algorithm a specified number times iteratively to obtain a collection of solution alternatives. In this study, `parallel programming strategy` is used in all of the above named algorithms. With this strategy, schedule generation takes the form of a step-by-step procedure. Each step is characterized with decisions about which activity and which of its technological alternatives is to schedule next, and with each scheduling effort a precedence, resource and cash flow feasible partial schedule is obtained. In classical sampling approaches, schedules are obtained in a straight-ahead manner, i.e. partial schedules generated at intermediate stages of schedule generation process are not evaluated. With new algorithms mechanisms and rules are introduced, which include generation and evaluation of partial schedules at pre - xix -specified stages in generating a feasible solution. Evaluation of partial schedules are carried out by calculating time, resource and cash-flow based lower bounds on project duration and by pruning partial schedules with which no better solutions than an existing one can be obtained with certainity. A rule is introduced to specify the stages in schedule generation at which partial schedules have to be evaluated. It's simply based on the number of activities that a partial schedule has to involve in order to get evaluated. In ARP2 and ARP3, only one partial schedule, obtained in each predetermined stage is evaluated. In case of pruning, the partial schedule is discarded and the procedure of generating a new one is started. The difference between ARP2 and ARP3 is that in ARP3 values of some parameters e.g. the value of Q or the priority criterion are changed at the evaluation stages according to some lower bound values i.e. ARP3 involves a triggering mechanism for some parameters. Algorithm ARP4 has a quite different structure than ARP2 and ARP3. With this algorithm schedules are generated stagewise by applying cuts in the process of sampling. At each evaluation stage, a predetermined number of partial schedules are generated in parallel. Then they are bounded and except a given number of dominant partial schedules all others are discarded. Sampling process is then continued to the next stage by generating a new set of partial schedules based only on dominant ones. An experimental investigation has been carried out to compare the effectiveness of the algorithms. With a simulation algorithm developed for this purpose 80 test problems with max. 45 activities, differing in size and network complexity and featuring specified charac teristics like `network density`, `topological ordering of nodes` and `network shape` have been generated. Experimental work covered following stages: Considering variability of activity durations, 35 priority rules are defined and applied with ÇÖK algorithm on each problem. None of the rules showed a superior perform ance in minimizing project duration, but rules based on activity starting and finishing times calculated in critical path analysis produced generally good results followed by `min. dynamic float` rule. Best rule selected was based on the `mean of the late starting times of activities` calculated by considering only shortest and only longest activity durations twice. In order to investigate the effect of the para meter Q and of priority rules in sampling procedures, ARP1 algorithm has been applied on selected test problems with different priority rules and by changing the value of Q each time. It's concluded that, with good priority rules and Q values higher than 0.5 better results could - xx -be obtained, as compared to less efficient priority rules which showed no significant changes in results when Q values are changed. For further applications, Q has given a value of 0,70 and the best rule stated above has been choosen. The application of ARP2, ARP3 and ARP4 on selected test problems by varying the number of partial schedule evaluation stages and the number of dominant partial schedules in ARP4 showed that bounding efficiency is not well enough on partial schedules involving less than 50% activities of a project. For further applications, it's decided to evaluate only partial schedules containing 50 and 75% of activities at two stages. Also, the appropriate bounds for the number of dominant partial schedules has been determined as 3 and 5, considering solution quality and computation times. The value 4 is selected for further applications. Applying all algorithms ön all test problems with precified values or parameters following results have been obtained: Even with small sample sizes of 35, all algorithms have performed well when best solutions obtained with them are compared with a single solution obtained with the best priority rule. Mean of best results regarding project durations differ by about 30% between ARP4 and best priority rule. Although no significant differences were observed between the means of best results obtained with ÇÖK and ARP1, ARP4 produced schedules with at least 10% shorter project durations in 99% confidence limits. Similarly, there are no significant differences between ARP2 and ARP3, but with these methods slight improvements in results were observed as compared to ÇÖK and ARP1 Evaluation of schedules according to cost criteria such as total project cost showed also that ARP4 is superiour against all other algorithms. As project duration gets shorter, the variability of different cost solutions at a specific project duration decreases because of resource restrictions, and with procedures effective in minimizing project duration the probability of obtaining a least cost solution gets higher. In the study, a sampling based new approach is suggested which enables the determination of the least cost curve under resource constraints without making exhaustive trials. The evaluation of results according to solution times indicated that ARP4 requires as much as 2,5 times more computational efforts as compared with ÇÖK and ARP1, but it showed a linearly increasing tendency with increased problem sizes. In general, its concluded that with procedures involving generation and bounds of partial schedules the performance of sampling approaches can be increased considerably and in future more use will be made of these approaches because of their flexibility in producing various solution alternatives. - xxi -