Repositorio Institucional de Documentos

Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es Proyecto Fin de Carrera Evaluación de reglas de prioridad para la asignación de recursos en la gestión de proyectos Fernando Alastuey González Noviembre 2012 Director: Tim Horenburg Ponente: Iván Lidón López Departamento de Ingeniería de Diseño y Fabricación Escuela de Ingeniería y Arquitectura Universidad de Zaragoza Lehrstuhl Fördertechnik Materialfluss Logistik Technische Universität München 1 Resumen En el presente documento se afronta el problema de la gestión de proyectos con restricciones de recursos llamado Resource-Constraint Project Scheduling Problem (RCPSP). Hace referencia a la gestión de cualquier proyecto en el que se tengan unos recursos por unidad de tiempo limitados y que por tanto no permitan la realización simultánea de todas las actividades en paralelo sino que haya que elegir un orden para la realización de las mismas. Este problema se ha planteado en numerosas ocasiones en el Departamento de Logística de la Universidad Técnica de Múnich, origen de la realización de este trabajo. El objetivo principal es realizar el proyecto empleando el menor tiempo posible y para ello se debe encontrar el orden más beneficioso para le ejecución de las actividades. Los factores a tener en cuenta no son solo la cantidad de recursos y materiales necesarios para la realización de cada una, sino también su duración, así como sus sucesores y predecesores. Para ello se utilizan las ´priority rules´ o reglas de prioridad que asignan a cada actividad un determinado valor y gracias a este valor, una prioridad con respecto a las otras actividades con las que compite. Para la realización de este proyecto se ha buscado en la bibliografía existente y se han implementado a través del programa Plant Simulation las 10 reglas de prioridad que según la documentación relativa a este tema mejor funcionan. Para hacer el estudio lo más riguroso posible, se han analizado y comparado 2040 proyectos con 10 ventanas de tiempo distintas para cada una de las 10 reglas de prioridad estudiadas, en total por tanto han sido simulados más de 200.000 proyectos. Por último se ha introducido un recurso novedoso en este tema al que se ha denominado recurso tipo área. Consiste en la introducción de una nueva restricción para la ejecución de las actividades. Se ha desarrollado para la gestión de proyectos que deban realizarse en una superficie determinada, por ejemplo la planta de una empresa que posee distintas máquinas. A cada actividad se le asigna una cierta zona de la empresa para ser desarrollada (requiere ser realizada por una determinada máquina). Así pues mientras haya otra actividad empleando esa zona requerida, no podrá ser ejecutada al no estar disponible este nuevo recurso y por tanto puede variar el orden preestablecido por las reglas de prioridad. Se considera que además de para la planificación de proyectos a realizar dentro de empresas, puede ser de gran importancia en la gestión en proyectos de obra (requerimientos de grúas, restringir el paso hacia determinados lugares en el que se están desarrollando actividades etc.) Los resultados obtenidos muestran que las reglas de prioridad que mejor funcionan son las llamadas Long Path Following (LPF) y Minimum Slack (MinSlack) y muestran una mejora sustancial con respecto a las reglas utilizadas en los proyectos realizados por el Departamento de Logística de la Universidad Técnica de Múnich. Además, se ha sentado una base en lo referente al recurso área que era la parte más novedosa de este trabajo para la futura investigación que será llevada a cabo por futuros alumnos de dicho centro. 2 3 Lista de contenidos. Resumen 1 Objetivo y contenidos del proyecto 5 Introducción 7 Marco teórico 9 Estudio empírico 11 Futuras investigaciones 15 Anexo A, documento original. 4 5 1 Objetivo y contenidos del proyecto El presente documento es una versión resumida del proyecto original realizado en la Universidad Técnica de Múnich, Alemania, entre los meses de mayo y octubre del año 2012 en el Departamento de Logística (Lehrstuhl Fördertechnik Materialfluss und Logistik) dirigido por el profesor Tim Horenburg. El documento original escrito en inglés y adjuntado como anexo, aporta información detallada, extensa y amplia, con ejemplos, figuras y tablas que ayudarán al lector a comprender el contenido de este trabajo de una manera más eficaz. El resto de la memoria se organiza como sigue. El capítulo 2 ofrece una breve introducción al problema de la gestión de proyectos con recursos limitados (RCPSP) en sus siglas inglesas. En el capítulo 3 se puede encontrar una breve aproximación teórica de las reglas de prioridad que son el método usado para determinar el orden de ejecución de las actividades, así como el nuevo recurso introducido en este trabajo que ha sido llamado Recurso Área, la forma en como ha sido diseñado y sus aplicaciones. Además, se introduce el sistema multi-agente que es el sistema aplicado para la resolución del RCPSP mediante el cual se asignan los recursos a las actividades para que sean realizadas. El capítulo 4 se centra en el desarrollo empírico del proyecto donde se incluye una breve descripción de los set de proyectos que van a ser simulados y probados para las diferentes reglas así como un breve análisis de los resultados obtenidos. Por último en el capítulo 5 se plantean las futuras lineas de investigación que complementen el estudio actual. El orden de los capítulos seguidos en esta memoria no se corresponde con el del proyecto original, pero debido a la brevedad del mismo, se ha creido conveniente adecuarlo de esta manera para facilitar la comprension del documento para el lector. Los objetivos para los que ha sido realizado este trabajo son dos. En primer lugar encontrar las reglas de prioridad que mejoren los resultados obtenidos por las reglas usadas en el Departamento de Logística de la Universidad Técnica de Múnich para la optimización de tiempos y presupuestos en sus proyectos. Los algoritmos realizados serán por tanto usados para la realización de los futuros proyectos que se vayan a llevar a cabo. El segundo objetivo que se persigue es la introducción del recurso área sobre el que futuros alumnos de la Universidad Técnica de Munich investigarán. Para ello se ha seleccionado una de las reglas de prioridad que mejor funciona que es la llamada Long Path Following (LFP) y se han realizado los proyectos una vez introducido el recurso área. Estos resultados servirán como base para la mejora de las reglas de prioridad que serán investigadas para la elaboración de los proyectos de logística y construcción que se llevan a cabo en el departamento. 6 7 2 Introducción Dado un proyecto cuyas actividades requieren una cierta cantidad de recursos, materiales y tiempo no variables a lo largo del desarrollo del mismo, el objetivo principal para el director del proyecto, que dispone de una cantidad de recursos limitada por unidad de tiempo, es reducir su duración programando las actividades en el orden más favorable. Este es el llamado Resource-Constraint Project Scheduling Problem (RCPSP) y las razones de buscar la minimización de la duración del proyecto son las siguientes:  La mayoría de los pagos se efectuan al final del proyecto y por tanto para reducir la cantidad de capital inmovilizado es importante concluir el mismo en el menor tiempo posible.  La calidad de las estimaciones disminuye con la distancia en el futuro para las que están hechas debido a la incertidumbre de la información y a los cambios en el marco de trabajo.  Terminar el proyecto lo antes posible reduce la posibilidad de sobrepasar fechas límite.  Cuanto antes se termine un proyecto, antes se liberan recursos para realizar nuevos proyectos o emprender nuevas acciones económicas. Es por tanto de vital importancia como puede observarse, la realización del proyecto en el mínimo tiempo posible. La forma de abordar el RCPSP es asignando a cada actividad un determinado valor y de acuerdo a este valor dichas actividades obtienen una prioridad con respecto a las otras que marca el orden de realización de las mismas. Este procedimiento de asignar diferentes valores a cada actividad se llama ´Priority Rule´ o en español Regla de Prioridad. Como resumen, el problema comprende la selección y realización de las actividades apropiadas cuando muchas compiten por los mismos recursos. 8 15 5 Futuras investigaciones Se ha probado en este documento que las reglas de prioridad que mejor funcionan son aquellas que utilizan el camino crítico para asignar valores a las actividades. La regla LPF da prioridad a aquellas actividades que están en el camino crítico en cada tiempo de negociación. Procedimiento parecido es llevado a cabo por la regla de prioridad MinSlack y como se ha comprobado también muestra buenos resultados. Otras reglas que también muestran buenos resultados han sido WCS y ACS cuya asignación de valores también está relacionada con el camino crítico. Debido a esto, se considera que los gestores de proyectos que quieran desarrollar nuevas reglas de prioridad deberían enfocar sus estudios en métodos que asignaran valores relacionados con el camino crítico. Como puede verse en el capítulo 4.4 del documento original, cuando dos actividades obtienen el mismo valor y por tanto tienen la misma prioridad, sería necesario la introducción de una nueva regla que se usase para romper estas igualdades. Este método eliminaría la ejecución aleatoria de una u otra actividad que es el método que se utiliza actualmente. Sería por tanto importante comprobar que pareja de reglas de prioridad arrojarían mejores resultados cuando fueran utilizadas para realizar proyectos. En lo concerniente al recurso del tipo área que ha sido introducido por primera vez en este estudio, se deberian crear nuevas reglas de prioridad para la realización de este tipo de proyectos de manera que ordenaran las actividades de una forma más eficiente y que por tanto mejorasen los resultados que se han obtenido. fml –Lehrstuhl für Fördertechnik Materialfluss Logistik Prof. Dr.-Ing. Dipl.-Wi.-Ing. W. A. Günthner Technische Universität München Diplomarbeit Evaluation of different priority rules for resource allocation in project scheduling Fernando Alastuey González Matr.-Nr.: 03296555 November 2012 Betreuer Lehrstuhl fml: Dipl.-Ing Tim Horenburg I 1 Abstract In this document, the Resource-Constraint Project Scheduling Problem (RCPSP) is going to be faced. It refers to the management of any project in which the amount of resources per unit time is limited and hence, it is not possible to schedule simultaneously every parallel activities but have to been prioriticaly chosen and executed. The main goal is to schedule the activities in the best order to make the duration of the project as short as possible taking into account not only the resources, duration and necessary materials but also the predecessors and successors tasks. To solve it a set of mathematical methods called Priority Rules are used. The way they work is assigning every task a value which determines the order of choice and execution for all of them. In this section a compilation of most of the Priority Rules that actually exist are going to be studied and explained with the help of an easy and short example of project to illustrate the reader how values are assigned to every activity and how are then they scheduled. The next step will be the simulation of the, according to the checked papers, 10 best Priority Rules and will be analyzed and compared for 2040 different projects in order to make the study as accurate as possible. The last part of the study will be the introduction of a new type of resource that has been called as Area´s resource. It consists in the introduction of a new constraint in the scheduling of the activities. It would be helpful when the project must be realized in a certain place with a limited area as for example the inside surface of a firma or the area in a building work. Every activity would have assigned a fixed place where they would be executed, as a concrete machine in a firma or a concrete crane while building. So as long as a running activity is using this place the task could not be executed and hence, the order of scheduling the activities may vary. It is considered that this resource would be very helpful and used in construction´s projects as well as in the layout planification of companies. II III 2 Acknowledgments This work has been carried out as my diploma thesis for the department of Fördertechnik Materialfluss Logistik from the Technische Universität München, Germany. It will also be considered as my final thesis in the Universidad de Zaragoza, Spain. My gratitude goes to prof. Dr-Ing. Dipl.-wi.-Ing Willibald A. Günthner and the whole department of Logistik in Munich, for giving me the opportunity to be part of it during the last six months, but specially to my “Betreuer” Tim Horenburg, who has allowed me to participate and work with him in this project. I would also want to thanks him for his time, his advice and for his endless patience with the german language and with the use of the software used in the project. I would also like to thank Iván Lidón, my supervisor, that from the distance has helped me to improve my work. Special consideration goes to my parents, brother, grandparents, uncles and cousines, for sacrificing for me and giving me so much whenever I need it. I am grateful also for the support, friendship and good moments lived with my spanish friends in Zaragoza and in Munich, specially to Adriana, Alejandro, Alvaro, Francho, Gonzalo, Jorge and Pablo. I would also like to thank my german friends whose help, affection and time have been of great confort and have made me not to feel the distance to Zaragoza. Finally I would like to thank Teresa for her patience, time, support and love, for his company and for everything she has sacrified to be with me. IV Contents V Contents 1 Abstract I 2 Acknowledgments III 3 Introduction 1 3.1 Problem and Motivation 1 3.2 Objective 2 3.3 Methodology 3 4 State of the Art & Related work 5 4.1 Historical review on project management 5 4.2 Resource-Constraint Project Scheduling Problem 5 4.3 Priority Rules 7 4.3.1 Theory and explanation of the priority rules 7 4.3.2 Selection of the choosen priority rules 32 5 About Plant Simulation 35 5.1 Introduction 35 5.2 The necessity of simulation 35 5.3 Plant Simulation in the thesis 36 5.4 Multi-Agent Scheduling System 36 5.4.1 Process agent 37 5.4.2 Resource agent 37 5.4.3 Bidding system 38 5.4.4 Time Window 38 5.4.5 Implementation of priority rules 39 5.5 Example of simulation 39 6 Results and Conclusions 43 6.1 Results and conclusions for the J30 set of projects 43 6.2 Results and conclusions for the J60 set of projects 47 6.3 Results and conclusions for the J90 set of projects 50 6.4 Results and conclusions for the J120 set of projects 53 6.5 Conclusions 55 Contents VI 7 Area Resource 57 7.1 Introduction 57 7.2 Theory and explanation 57 7.3 Method applied 58 7.3.1 Requirements for the implementation 58 7.3.2 Area´s resource agent 58 7.3.3 Implementation 59 8 Conclusions 63 8.1 Results for the J30 set of projects 64 8.2 Results for the J60 set of projects 65 8.3 Results for the J90 set of projects 67 8.4 Results for the J120 set of projects 68 8.5 Conclusions 69 9 Future investigations paths 71 Bibliography 73 List of figures 77 List of tables 79 Appendix A 1 1 3 Introduction 3.1 Problem and Motivation Project planning and scheduling has become an important management tool for today´s complex business and manufacturing systems. Models and methods from project planning play a vital role in such different tasks as, e.g. the re-design of business and work processes and finite scheduling of manufacturing systems (cf. (Adelsberg and Kanet, 1991; Tobias, 1991; Stadtler and Wilhelm, 1993)). The core of project planning is the Resource-Constrained Project Scheduling Problem (RCPSP). It adresses the question of how activities which are interrelated by technological and multiple capacity constraints have to be time-phased in order to accomplish a prespecified management goal. [Kol-96] Assuming a complete project with a limited number of activities which everyone of them needs a certain amount of resources, material and have a estimated duration which are not supposed to vary during the course of the project, the main goal for a project manager that has limited resources available for every period of time is to reduce the makespan of the project scheduling the activities in the best proper order. The objective of makespan minimization is due to several reasons: Most of the income payments are made at the end of the project, therefore to reduce the amount of tied up capital is important to finish the project as early as possible. The quality of forecasts decrease with the distance into the future for which are made becasuse of data uncertainty and environment changes. Finish the product as soon as possible reduces the possibilities of deadlines violation. The earliest the project is finished, the earliest the resources available are freed to undertake new projects or new economic actions. [Kol-96] 3 Introduction 2 In order to deal with the problem of the RCPSP many different studies and efforts have been undertaken. The way to solve the problem is assigning every activity a determined value according to its priority and execute them in the proper order. The procedure of assigning the different values for every task is called `Priority Rule´. To sum up, the problem involves choosing and executing the „proper“ activities when several compete for the same resources. To solve the RCPSP problem in a proper way, project managers prefer the heuristic dispatching rules rather than the exact or optimal ones. This question lies on the fact that exact procedures are limited in the size of the project due to the complexity and the big amount of operations the algorithm sould carry out with. Hence, it is not possible to calculate a big project with this procedures in a reasonable amount of computation time [Sim-96]. In the other hand priority rules have the advantage of being intuitive and very robust and much faster in terms of computational effort. Besides, available software provides the project manager the opportunity to define its own priority rules and therefore the possibility to choose the most appropiate one for the project that sould be carried out. 3.2 Objective The main goal of this document is to give the reader an insight into the working of the project management and specifically in the RCPSP as well as to introduce the problem of the Area´s resource. This document will offer information about the obtained results for the different priority rules and could be used to choose the most appropiate one according to the characteristics of the project the reader sould face with. The objective of this writting will be also to introduce the Area Resource to the cientific comunity in order to make possible to solve in the best propper way those building work´s projects which are highly affected by surface constraints. 4.3 Priority Rules 9 Table 4-1: RSM- Duration and Latest Start Time Activity Duration LST 1 3 2 2 3 2 3 1 4 4 2 3 5 5 0 Once the LST is known, the value for the first activity is calculated by the RSM as follows. v(1) = max {0, tn + d1 – LST2, tn + d1 – LST3, tn + d1 – LST4, tn + d1 – LST5}= max {0, 0 +3 – 2, 0 +3 – 4, 0 +3 – 3, 0 +3 – 0 }=3 (3-2) The values for all activities as well as the priority in scheduling the activities are shown in table A-2 Table 4-2: First iteration for the RSM priority rule Activity Duration LST Value v(j) Priority 1 3 2 max {0, 1, -1, 0, 3}=3 3 2 3 2 max {0, 1, -1, 0, 3}=3 3 3 1 4 max {0, -1, -1, -2, 1}=1 1 4 2 3 max {0, 0, 0, -2, 2}=2 2 5 5 0 max {0, 3, 3, 1, 2}=3 3 Then activity 3 is first scheduled. As there are no more available resources, the second iteration begins when activity 1 is finished, at tn=1. 4 State of the Art & Related work 10 Table 4-3: Second iteration for the RSM priority rule Activity Duration LST Value v(j) Priority 1 3 2 max {0, 2, 1, 4}=4 2 2 3 2 max {0, 2, 1, 4}=4 2 4 2 3 max {0, 1, 1, 3}=3 1 5 5 0 max {0, 4, 4, 3}=4 2 The next activity in been scheduled is now activity 4. As activity 4 needs only the resource of type B if another activity needs only resource A could be scheduled simultaneously. Thus the only activity that needs resource A is activity 2 and is then scheduled. The process continues and the project is finally scheduled as shown in the picture below with a total duration of 11 units time. Critical path is represented by the arrows involving activities 1,3,4,5. Figure 4-2: Project solution for the RSM priority rule .2 Improved Resource Scheduling Method (IRSM) It was created and published in [Kol-96]. This priority rule divides the set of activity pairs APn into three different groups: Generally Forbidden Pairs (GFPn) contains the set of activities that due to resource constraints can never be scheduled simultaneously. Termporarily Forbidden Pairs (TFPn) contains the set of activities that can not be scheduled simultaneously because of a lack of the resources available at the schedule time. Currently Schedulable Pairs (CSPn) contains the set of activities that can be scheduled simultaneously at the schedule time. 4.3 Priority Rules 11 The time in which a pair of activities will be scheduled simultaneously depends on the group they belong to. ∏(i,j) is the earliest time for any activity pair to be scheduled simultaneously and is calculated as follows. If the pair belongs to the GFPn, ∏ (i,j) = ∞ and if it belongs to the CSPn, ∏ (i,j) = tn. For the activities in the TFPn group the ∏ (i,j) must be calculated according to the following formulas. ∏´(i,j) = min{τ Σ khr + πKr ≥ kir + kjr , τ=tn ,…, T/ }, (i,j) Є TFPn and h Є An /FTh <n (3-3) ∏ (i,j) =max { ∏´(i,j) / r Є R}, (i,j) Є TFPn. (3-4) The earliest time to schedule activity j if activity i is started at tn is for every kind of group of pairs as follows. E(i,j)=min{tn + di , ∏ (i,j) Є APn} (3-5) Once E(i,j) is calculated, the value assigned to an activity j is equal to v(j) = max { 0, E(i,j)-LSTi /(i,j) Є APn} (3-6) and the activity with the minimum value is selected. That means that the scheduled activity induces the minimum increase of the precedence based lower bound for the not chosen activities in the decision set. In order to clarify and make easy for the reader to understand this priority rule, a new example will be shown. In the first iteration tn=0 and as none of the resources have already been used, there are only two different cases of pairs to study, GFPn and CSPn. An example of GFPn can be studied with the pair of activities 1 and 3 and as told above. ∏ (1,3) = ∞ (3-7) E(1,3)= min{tn + d1 , ∏ (1,3) Є APn}= min{0 +3 , ∞ Є APn}= 3 that means that scheduling activity 1 that has a duration of 3 periods of time, induces a delay of 3 periods of time to the activity 3. An example of CSPn can be studied with the pair of activities 2 and 4. ∏ (2,4) = 0 (3-8) 4 State of the Art & Related work 12 E(2,4)=min{tn + d2 , ∏ (2,4) Є APn}= min{0 +3 , 0 Є APn} = 0 that means that scheduling activity 2 that has a duration of 3 periods of time, does not induce a delay in the activity 4. Once calculated E(i,j) for every pair of activities, it is possible to assign the proper value according to the IRSM priority rule to every activity and hence the priority for all of them. This is done in the table below. Table 4-4: First iteration for the IRSM priority rule Activity Duration LST Value v(j) Priority 1 3 2 max {0, 1, -1, 0, 3}=3 4 2 3 2 max {0, 1, -1, -3, 0}=1 1 3 1 4 max {0, -1, -1, -2, 1}=1 1 4 2 3 max {0, 0, -2, -2, 2}=2 3 5 5 0 max {0, 3, -2, 1, 2}=3 4 As both activities 2 and 3 have the same priority it will depend on the software to schedule one or the other in first case. In the example here shown the study will be carried out scheduling activity 3 in first place, but at the end of it both possibilities will be represented. Scheduling activity 3 do not allow to schedule any other activity simultaneously therefore the second iteration must be started at tn=1 when it would has finished. The values for the second iteration are represented in the table below. Table 4-5: Second iteration for the IRSM priority rule Activity Duration LST Value v(j) Priority 1 3 2 max {0, 2, 1, 4}=4 3 2 3 2 max {0, 2, -2, 1}=2 1 4 2 3 max {0, 1, -1, 3}=3 2 5 5 0 max {0, 4, -1, 3}=4 3 4.3 Priority Rules 13 The next activity in been scheduled is now activity 2. As activity 2 needs only the resource of type A if another activity needs only resource B could be scheduled simultaneously. Thus the activities that need resource B are 4 and 5 and as task 4 has more priority than 5 then is scheduled. The process continues and the project is finally scheduled as shown in the picture below with a total duration of 11 units time. The new Critical path considering resources is represented by the arrows involving activities 1,3,4,5. Figure 4-3: First solution for the IRSM priority rule Figure 4-4: Second solution for the IRSM priority rule .3 Minimum SLacK (MSLK) It is a classical priority rule that gives preference to those activities which are in the critical path or whose LST is close to the schedule time. The value is given according to the formula v(j)= LSTj – tn (3-9) and the activity with the minimum value is selected. [Kol-96] For the given example the values for the first iteration (tn=0) can be seen in table A-6 4 State of the Art & Related work 14 Table 4-6: First iteration for the MSLK priority rule Activity Duration LST Value v(j) Priority 1 3 2 2-0=2 2 2 3 2 2-0=2 2 3 1 4 4-0=4 5 4 2 3 3-0=3 4 5 5 0 0-0=0 1 Then activity 5 is first scheduled. As it only requires resource from type B, activity 2 is also scheduled. After finishing activity 2, as none of the remaining tasks employs only resource A, the second iteration will be started at tn=5. The process continues scheduling activity 2, after that 4 and activity 3 is left for the end. Critical path is represented by the activities 5, 3, 2, 1 and the duration is 11 periods of time. Figure 4-5: Project solution for the MSLK priority rule .4 Worst Case Slack (WCS) This priority rule was created and first published in Kolisch (1996). It combines concepts used in the IRSM with the fundaments of the MSLK. The priority value assigned to every activity according to the WCS is as follows. v(j) = LSTj - max { E(i,j)/(i,j) Є APn}. (3-10) With E(j,i) the earliest time to schedule activity j if activity i is started at tn calculated in the same way as fort he IRSM. The activity with the minimum value is selected. [Kol-96] The WCS priority rule would solve the example as follows. 4.3 Priority Rules 15 Table 4-7: First iteration for the WCS priority rule Activity Duration LST Value v(j) Priority 1 3 2 2- max {3,3,3,3}=-1 2 2 3 2 2- max {3,3,0,0}=-1 2 3 1 4 4- max {1,1,1,1}=3 5 4 2 3 3- max {2,0,2,2}=1 4 5 5 0 0- max {5,0,5,5}=-5 1 Then activity 5 is first scheduled. As it only requires resource from type B, activity 2 is also scheduled. After finishing activity 2, as none of the remaining tasks employs only resource A, the second iteration will be started at tn=5. The process continues scheduling activity 2, after that 4 and activity 3 is left for the end. Critical path is represented by activities 5, 3, 2, 1 and the duration is 11 periods of time. Figure 4-6: Project solution for the WCS priority rule .5 Average Case Slack (ACS) It is also created and first used in [Kol-96]. It combines as well concepts used in the IRSM with the fundaments of the MSLK. The priority value assigned to every activity according to the ACS is v(j) = LSTj – Σ(i,j )Є APn E(i,j) (3-11) Dn is the number of activities in the decision set and the activity with the minimum value is selected. For the given example the values for the first iteration (tn=0) can be seen in table 3-8 4 State of the Art & Related work 16 Table 4-8: First iteration for the ACS priority rule Activity Duration LST Value v(j) Priority 1 3 2 2- ¼(3+3+3+3)= -1 2 2 3 2 2- ¼(3+3+0+0)= 1/2 3 3 1 4 4- ¼(1+1+1+1)= 3 5 4 2 3 3- ¼(2+0+2+2)= 3/2 4 5 5 0 0- ¼(5+0+5+5)= -15/4 1 Now activity 5 is first scheduled. As it only requires resource from type B, activity 2 is also scheduled. After finishing activity 2, as none of the remaining tasks employs only resource A, the second iteration will be started at tn=5. The process continues scheduling activity 2, after that 4 and activity 3 is left for the end. Critical path is represented by the activities 5, 3, 2, 1 and the duration is 11 periods of time. Figure 4-7: Project solution for the ACS priority rule .6 Shortest Processing Time (SPT) It is a classical priority rule that gives priority to the shortest activities. The value is calculated with the formula v(j) = dj (3-12) and the activity with the minimum value is then scheduled. [Sim-96] In the studied example, the first iteration is again calculated for tn=0 and the values obtained as well as the priority are shown in the following table. 4.3 Priority Rules 17 Table 4-9: First iteration for the SPT priority rule Activity Duration LST Value v(j) Priority 1 3 2 3 3 2 3 2 3 3 3 1 4 1 1 4 2 3 2 2 5 5 0 5 5 In the first iteration the actvity 3 is the first in been scheduled. The project will follow executing in tn=1 activity 4 and 2. Later in tn=3 activity 5 would be scheduled and the last one would be activity 1. The critical path has a duration of 11 periods of time and is represented by activities 1, 4, 5, 1. Figure 4-8: Project solution for the SPT priority rule .7 Maximum Activity Duration (MaxDur) It is another classical priority rule that in opposition to the SPT gives priority to the longest activities. The value given to every task is calculated with the formula v(j) = dj (3-13) and the activity with the maximum value is then scheduled. [Sim-96] In the studied example, the first iteration is again calculated for tn=0 and the values obtained as well as the priority for every task are shown in the table 3-10. 4 State of the Art & Related work 18 Table 4-10: First iteration for the MAxDur priority rule Activity Duration LST Value v(j) Priority 1 3 2 3 2 2 3 2 3 2 3 1 4 1 5 4 2 3 2 4 5 5 0 5 1 In the first iteration the activity 5 that has a duration of 5 periods of time will be first scheduled. As it only needs resources from type B, activity 2 will also be executed. Then activity 1 will be scheduled in tn=5 and activities 4 and then 3 will be left for the end. The project duration is 11 periods of time and critical path is formed by tasks 5, 1, 4 and 3. Figure 4-9: Project solution for the MAxDur priority rule .8 Greatest Resource Demand (GRD) This priority rule was developed to avoid potencial bottlenecks actvities. It takes into account not only the amount of resources the activity needs but also the duration. The value is assigned to every task according with the formula v(j) = dj Σk=1 to K Rjk (3-14) being R the number of resources per period time and k the different types of resources and the activity with the maximum value is first scheduled. [Sim-96] The GRD priority rule would solve the example as follows. 4.3 Priority Rules 25 Table 4-17: First iteration for the GCRR priority rule Activity Duration EST Value v(j) Priority 1 1 0 1*1+3*2=7 3 4 3 0 3*1=3 2 5 2 0 2*1=2 1 The highest priority is given to activity 5 which is then scheduled. As there are no available resources for activity 4 to be scheduled simultaneously with activity 5, in the first iteration activity 1 will also be scheduled. Following the process as explained, the SCRR yields the following solution. Critical path is now delimited by activities 5, 2, 3 and 4 and the duration of the project is 11 periods of time. Figure 4-16: Project solution for the GCRR priority rule .13 Greatest Number of Successors (GNS) This priority rule focuses on the number of succesors every activity have. The value assigned then is simply the total (not only inmediate) number of successors and the activity with the biggest value is then chosen. Hence, this priority rule gives priority to those activities that has a big amount of successors in order to eliminate or reduce possible bottle-ties. [Kum-98] Scheduling the example project according to this priority rule will be as shown below. 4 State of the Art & Related work 26 Table 4-18: First iteration for the GNS priority rule Activity Duration EST Value v(j) Priority 1 1 0 2 1 2 3 1 1 2 3 3 4 0 3 4 3 0 0 3 5 2 0 0 3 As can be sawn the highest priority yields on activity 1 an hence is first scheduled. The problem now is that both activity 4 and activity 5 due to resource availability could also been scheduled and have the same priority. Hence two different solutions for the project could be reached. Both solutions are shown in the figures below. Figure 4-17: First solution for the GNS priority rule Figure 4-18: Second solution for the GNS priority rule The first one involves scheduling activity 4 first and has a duration of 9 periods of time whereas scheduling activity 5 simultaneously with activity 1 will decrease the duration in 1 period of time. 4.3 Priority Rules 27 The critical path in the first solution is formed by activities 4, 2 and 3 and in the second solution by activities 5, 2 and both 3 and 4. .14 Smallest Number of Successors (SNS) As for the previous priority rule, the value for every task is assigned according to the number of total successors but the difference here is that the activity with the highest priority is the activity with the minimum instead of the maximum number of successors. [Kum-98] Then for the given example the solution of he project would be as follows. Table 4-19: First iteration for the SNS priority rule Activity Duration EST Value v(j) Priority 1 1 0 2 5 2 3 1 1 4 3 3 4 0 1 4 3 0 0 1 5 2 0 0 1 Both activity 4 and 5 has the highest priority but due to a lack of the amount of resources only one of them could be first scheduled. So again 2 differents ways of solving the project could be reached. Figure 4-19: Two possible solutions for the SNS priority rule 4 State of the Art & Related work 28 As can be shawn, duration for both is 11 periods of time and therefore none of them yields good results. .15 Rank Positional Weight (RPW) It is a classical priority rule that focuses in the duration of the activty and the duration of all its successors. Hence, this priority rule gives usually priority to those activities which have many successors with a long duration. The value then given for every activity is the sum of its duration plus the duration of all its successors as can be san in the formula below. [Kum-98] v(j) = dj + Σn=1 to N dn where N is the total number of successors. (3-16) The table below shows the result for the first iteration for the studied project example. Table 4-20: First iteration for the RPW priority rule Activity Duration EST Value v(j) Priority 1 1 0 1+3+3 = 7 1 2 3 1 3+3=6 2 3 3 4 3 3 4 3 0 3 3 5 2 0 2 5 Then the activity first scheduled is activity 1 and simultaneously is also executed activity 4. The process follows then with activity 2 and at the end activities 3 and 5 will be scheduled simultaneously. The project duration is 9 periods of time and the activities in the critical path are now 4, 2 and 3. Figure 4-20: Project solution for the RPW priority rule 4.3 Priority Rules 29 .16 Long Path Following (LPF) It is another classical rule that focuses in the duration of the activities and the duration of all its successors but the difference with the RPW is that takes only into account not all the successors but only those that will be in the critical path for the evaluated activity. That means starting with the evaluating activity which is the longest path among all its successors to accomplish the project. Hence, this priority rule gives priority to those activities in the critical path. [Sti-78] For the given example, the project would be solved as follows. Table 4-21: First iteration for the RPW priority rule Activity Duration EST Value v(j) Priority 1 1 0 1+3+3 = 7 1 2 3 1 3+3=6 2 3 3 4 3 3 4 3 0 3 3 5 2 0 2 5 As can be sawn to finish the project from the point of view of activity 1, the path to accomplish the project is adding to its duration the duration of activity 2 and 3. The difference with the RPW could be clearly sawn in the following example. The reader has to imagine that another activity of duration 4 (activity 6) in parallel with activity 3 is now added. The value that the RPW would assign to activy 1 would be 7+4=11 but according to the LPF the value would be determined between the maximum of the two possible paths to accomplish the project. The first path will be as sawn before involving activities 1, 2 and 3 and would have a duration of 7 periods of time. The second path would be involving activities 1, 2 and now instead of activity 3, activity 6 and hence the duration would be of 8 periods of time. As 8 is bigger than 7, the value that the LPF would assign to activity 1 would be 8. Following now with the studied example (without activity 6) activity 1 with a value of 7 would have the highest priority and therefore would be first executed. Simultaneously with activity 1, task 4 would also be scheduled. The solution for the project would be as follows. 4 State of the Art & Related work 30 Figure 4-21: Project solution for the RPW priority rule The total duration for the project is 9 periods of time and the activities that form part of the critical path are now 4, 2 and 3. .17 Great Number of Inmediate Successors (GNIS) In this rule the priority is given to the activity that has the largest number of inmediate successors. It is a easy and functional priority rule that try to avoid bottle-ties. [Kum-98] As done with the previous priority rules, a example for the studied project will be solved. Table 4-22: Iteration for the GNIS priority rule Activity Duration EST Value v(j) Priority 1 1 0 1 1 2 3 1 1 1 3 3 4 0 3 4 3 0 0 3 5 2 0 0 3 Both activities 1 and 2 have the highest priority but in this case as activity 2 is a successor from activity 1, only activity 1 can be scheduled. But in the oder hand activity 4 and 5 have the same priority and hence two differents solutions could be reached as can be sawn in the figure below. 4.3 Priority Rules 31 Figure 4-22: Project solutions for the GNIS priority rule In the example the second solution yields better results with a duration of 8 periods of time instead of 9. .18 Smallest Number of Inmediate Successors (SNIS) The way this priority rule assigns values to the activities is the same as the previous priority rule but the activity with the minimum successors is now chosen. [Kum-98] It is not a very efficient rule as the reader could see at the end of the example. Table 4-23: Iteration for the GNIS priority rule Activity Duration EST Value v(j) Priority 1 1 0 1 4 2 3 1 1 4 3 3 4 0 1 4 3 0 0 1 5 2 0 0 1 As with other examples, according to the priority of the different activities, two possible solutions can be reached. The first solution is scheduling activity 4 firstly as well as due to resource availability activiy 1. The second solution would be schedul- 4 State of the Art & Related work 32 ing in first place activity 5 as well as activity 1. The two possible solutions have the same duration and can be sawn in the figure below. Figure 4-23: Two possible solutions for the SNIS priority rule As can be sawn, duration for both is 11 periods of time and hence, none of them yields good results. 4.3.2 Selection of the chosen priority rules In this document, 10 different priority rules have been implemented and studied with the help of the software Plant Simulation. According to the paper from Kum Khiong Yang [Kum-98]: The results show that project environment affects only the performance differences but not the grouping of the better dispatching rules. The greatest number of successors, rank postional weight, greatest cumulative resource requirement and minimum activity slack dispatching rules consistently perform better than the other dispatching rules, unaffected by the accuracy of the estimated activity durations. Hence, those priority rules have been studied with the exception of the Rank Positional Weight that has been replaced by the Long Path Following priority rule because of their similarity and because was already used in the Technische Universität München as well. The other activities performed are resource scheduling method, improved resource scheduling method, worst case slack and average case slack because according to Kolisch [Kol-96] were some of the best priority rules. 4.3 Priority Rules 33 The latest finish time priority rule has also been implemented due to two different reasons. First reason is that it assigns values in a very easy way and hence it is very easy to implement. The second and more important is because it requires a low amount of computational calculations and therefore as it yields not bad solutions it is a good priority rule to use to compare with solutions reached by other priority rules. 4 State of the Art & Related work 34 5.5 Example of simulation 41 As can be sawn the result is the same and thus it can be said that the algorithm is done in the proper way. In the figure A-21 the reader could see that there are 32 activities but activity p101_1 and p101_32 correspond to the activities Start and End which in the self-calculated case are no numbered. As an small example, activity 1 (Start) has three successors that are activities 2, 3 and 4 so in the first iteration both three could be selected. Activity 2 has a duration of 8 units of time and its Latest Finish Time (LFT) is 7. The duration for activities 3 and 4 is 4 and 6 and the LFT is 0 and 1 respectively. The values then assigned to the activities are: v(2) = max { 0, 8, -1}=8 (4-1) v(3) = max { 0, -3, -1}=0 (4-2) v(4) = max { 0, -7, 0}=0 (4-3) The activity selected is the one that induces the minimum increase of the precedence based lower bound for the not chosen activities in the decision set. In the example above, activity 3 and 4 have then the maximum priority. As there are enough resources for both of them but not for activity 2 as well, activities 3 and 4 are first executed. The next scheduling time is at t=4, when activity 3 is finished. Now the activities that are available to be scheduled are 2, 7, 8 and 13 and the values assigned to them: v(2) = max { 0, -16, -9, -8}=0 (4-4) v(7) = max { 0,-3, 0, - 8}=0 (4-5) v(8) = max { 0, -3, -16, -8}=0 (4-6) v(13) = max { 0, -3, -16, 0}=0 (4-7) As can be sawn, the value for every activity is the same and hence, all of them have the same priority. As there are enough resources to schedule all of them simultaneously, at time t=4 activities 2, 7, 8 and 13 are executed. The procedure continues at the scheduling time t=6, when activity 4 is just finished. At this scheduling time activities 5, 9 and 10 are ready to be executed. Now activity 10 is executed and the projects goes on. 5 About Plant Simulation 42 The reader is encouraged to follow the procedure by itself in order to finish the project and check its results with the obtained here. The project is finally accomplish after 43 units of time, which for this problem is the minimum time. As the reader could have sawn in the second iteration, the values assigned to the four activities were the same and hence, the priority is not clearly defined. That was not cause for concern because the amount of resources available was enough to schedule all of them at the same time. A possible way to solve this problem would be explained in the chapter 8, when talking about future investigations paths. 6.1 Results and conclusions for the J30 set of projects 43 6 Results and Conclusions As told in chapter 3.3.2 ten different priority rules have been implemented and studied for the J30, J60, J90 and J120 standard set of projects. The J30, J60, J90 and J120 were generated by Kolisch and Sprecher in 1997 with the program ProGen network generator in order to be used in future investigations to standardize the study of the RCPSP among others. They are available in the website http://129.187.106.231/psplib/. The J30, J60 and J90 problem sets all have 480 projects with four resource types and 32, 62 and 92 activities but the first and the last activity which represent the beginning and the end of the project has neither duration nor resource requirements and therefore it is said that for the J30, J60 and J90 the number of non-dummy activities is 30, 60 and 90. The J120 problem set is composed of 600 different projects with five resource types and 120 non-dummy activities. (references) 6.1 Results and conclusions for the J30 set of projects Table 6-1: Average deviation from optimum for different time windows, J30 TW GCRR LPF RSM GNIS GNS IRSM WCS ACS MSLack LFT 0 3,30 3,02 3,55 4,75 3,21 3,49 3,49 3,18 3,02 2,79 1 3,32 2,91 3,55 5,01 3,11 3,48 3,37 3,20 2,91 2,67 2 3,65 3,14 4,22 5,37 3,25 3,76 3,61 3,28 3,14 2,90 3 3,95 3,26 5,16 5,92 3,51 4,19 3,83 3,60 3,26 3,20 4 4,29 3,44 6,33 6,41 3,94 4,87 4,03 3,74 3,44 3,57 5 4,62 3,67 7,21 7,11 4,27 5,20 4,23 3,86 3,67 4,03 6 4,92 3,93 8,13 7,75 4,64 5,70 4,46 4,04 3,93 4,29 7 5,14 4,04 9,05 8,11 4,87 5,97 4,49 4,21 4,04 4,36 8 5,20 4,10 9,76 8,44 5,13 6,37 4,56 4,36 4,10 4,57 9 5,32 4,10 9,76 8,47 5,15 6,59 4,65 4,33 4,10 4,80 6 Results and Conclusions 44 Figure 6-1: Average deviation from optimum for different time windows, J30 The table shows for every studied priority rule the average deviation from the optimum solution for ten different values of time window. The way of doing it is as follows. For the 480 different projects which the J30 problem set is composed of, the projects have been executed using a selected priority rule for the same time window value and this has been repeated for the different values of time window and for every priority rule, that means 4800 projects for every priority rule, 48000 projects altogether. Consequently, the table yields the efficiency of every priority rule to face projects with different time windows. The graphic clarifies and gives form to the numbers in order to make a visual representation of the results. The x axis represent the different values of time window whereas the y axis represent the average deviation from optimum. As can be seen, the efficiency for every priority rule diminishes as the value of the time window increases. Remarkably negative is the effect of this increase in the duration of the projects scheduled using the RSM and GNIS priority rules. Those priority rules are then not adequate to solve projects in which high values of time windows are required. In addition to this low efficiency with high values, with low values of time window there is an appreciable difference of two periods of time in compari- 0,00 2,00 4,00 6,00 8,00 10,00 12,00 0 1 2 3 4 5 6 7 8 9 GCRR LPF RSM GNIS GNS IRSM WCS ACS MinSlack LFT 6.1 Results and conclusions for the J30 set of projects 45 son with the other rules used and hence, it is possible to state that RSM and GNIS priority rules are not the right priority rules to execute the J30 set of projects or at least they are not as good as the oder rules used. Lightly better are the results obtained while executing projects with IRSM. Although at the beginning the deviation from optimum is not big, as long as the time window values increase, the IRSM yields poor results. Better results than the three priority rules previously analyzed are yielded by GCRR and GNS. Both two have a similar behavior suffering an increase of 2 periods of time along the values of the time window. The deviation from the optimum at the beginning of the chart is about 3 periods of time whereas at the end, with values of time windows of 8 and 9, the deviation is around 5 periods of time. They are not the priority rules that better solutions offer, but in comparison with the previously studied rules (RMS, GNIS and IRSM) the efficiency is much higher. The WCS and ACS priority rules yield little bit better results than the obtained by GCRR and GNS. For this two priority rules the increase of the deviation from the optimum along the different values of time window is only of 1 period of time, starting with a deviation around 3 periods of time and finishing with a deviation of 4 periods of time for the values of time window 8 and 9. According to the chart, LFT and MinSlack as well as LPF are the priority rules that better solutions offer for the studied projects. Nevertheless the behavior along the different values of time window is very different. Although LFT yields the better solution for projects with values of time window of from 0 to 3 with an average deviation from the optimum smaller than 3, the increase of the deviation along the chart has a steep slope that makes the rule inefficient for big values of time window. On the other hand, the results obtained using the MinSlack and LPF priority rules show the opposite behavior. At the beginning, the duration of the projects carried out is not the shortest one, but as can be seen, the effectiveness of these priority rules do not depend highly on the different values of time window and hence, from values bigger than 4 the solutions offered are the best ones. Although the results are exactly the same, that means that the activities are ordened in the same way, the way of assigning values as can be seen in the chapter 3.3.1 to the activities is different for both of them. 6 Results and Conclusions 46 Table 6-2: Average deviation from optimum over all time windows, J30 Then as a conclusion, this J30 project experiment reject the WCS, RSM and GNIS as a way to obtain good results when scheduling this type of projects. The results obtained using the other priority rules shows no big differences. Although for small a values of time windows the LFT yields the better results, LPF and MinSlack have a smaller general average deviation and hence if the time window for a project is not clearly specified it would be better to schedule the project using LPF or MinSlack instead of the other rules. Figure 6-2: Average deviation from optimum for th J30 set of projects. 0,00 1,00 2,00 3,00 4,00 5,00 6,00 7,00 8,00 1 GCRR LPF RSM GNIS GNS IRSM WCS ACS MinSlack LFT GCRR LPF RSM GNIS GNS IRSM WCS ACS MSLack LFT Average 4,37 3,56 6,67 6,73 4,11 4,96 4,07 3,78 3,56 3,72 6.2 Results and conclusions for the J60 set of projects 47 6.2 Results and conclusions for the J60 set of projects Table 6-3: Average deviation from optimum for different time windows, J60 TW GCRR LPF RSM GNIS GNS IRSM WCS ACS MSLack LFT 0 5,26 4,85 6,03 7,65 5,20 6,17 5,33 5,17 4,85 4,93 1 5,33 4,57 6,71 8,39 5,07 6,27 5,08 4,71 4,57 4,69 2 5,68 4,62 8,18 9,21 5,52 6,75 5,09 5,03 4,62 4,88 3 6,31 5,02 9,79 10,26 6,03 7,97 5,51 5,15 5,02 5,39 4 6,90 5,49 12,25 11,55 6,54 8,82 5,74 5,72 5,49 6,07 5 7,53 5,76 14,56 12,70 7,25 9,67 6,05 5,65 5,76 6,55 6 7,96 6,06 16,35 13,49 7,58 9,96 6,25 6,00 6,06 6,96 7 8,12 6,19 17,71 13,94 7,90 10,61 6,41 6,08 6,19 7,36 8 8,16 6,33 18,77 14,36 8,21 10,65 6,57 6,24 6,33 7,57 9 8,21 6,34 18,61 14,74 8,11 11,29 6,64 6,20 6,34 7,71 Figure 6-3: Average deviation from optimum for different time windows, J60 0,00 2,00 4,00 6,00 8,00 10,00 12,00 14,00 16,00 18,00 20,00 1 2 3 4 5 6 7 8 9 10 LPF RSM GNIS GNS IRSM WCS ACS MinSlack LFT GCRR 6 Results and Conclusions 48 They way of proceeding is the same as with the J30 project. Although the average deviation from the optimum for every priority rule is bigger, it does not mean that the priority rules do not work properly for this set of projects. As the projects consist now of 60 non-dummy activities, the duration of the project is longer and hence, the deviation from the optimum in general terms is bigger. Though the percentage deviation from the optimum stays as before. As with the J30 set of projects, RSM and GNIS yield poor results not only for big values of time windows but also for small ones. The priority rule GNIS have a continous slope during the whole chart, whereas the RSM offers better results at the beginning but the increase of the deviation along the different values of time window is much bigger and at the end the results obtained are even worst. Then, it is possible to state that RSM and GNIS priority rules are not the right priority rules to execute the J60 set of projects or at least they are not as good as the oder rules used. The IRSM yields better results than the three priority rules previously commented. For small values of time windows, the average deviation from the optimum is 6 periods of time but at the end of the graphic the deviation reaches up to values around 10 which is then clearly worst than the priority rules that would be explained below. GNS and GCRR have now a similar behavior. At the beginning of the chart, they offer good results but the increase along the different values of time windows is a little bit more notable than the remaining priority rules. Unlike the conclusions obtained for the J30 set of projects, now the LFT can not be considered as one of the best priority rules. The results obtained for small values of time windows are still good, but the increase of the deviation from the optimum along the chart is considerably bigger than for the best priority rules. LPF and MinSlack yield again the same results during the whole chart. They offer the best solutions for the four first values of time window and for big values the increase of the deviation from the optimum reach values of 6 periods of time which as can be seen in the chart, is smaller than for the already commented priority rules. Hence, for this set of projects they kept as two of the best priority rules studied. The ACS shows a different behavior as the LFP and MinSlack priority rules. Whereas for the first values of time window LPF and MinSlack yield the better solutions, the 6.2 Results and conclusions for the J60 set of projects 49 results obtained for values bigger than 3 are lightly better and thus it is also considered as one of the best priority rules. Table 6-4: Average deviation from optimum J60 Then as a conclusion, this J60 project experiment reject the RSM and GNIS as a way to obtain good results when scheduling this type of projects. The results obtained using the other priority rules shows no big differences. The minimum average deviation from the optimum is obtained when scheduling the projects with the priority rules LPF and MinSlack. Lightly bigger is the average deviation of the ACS and WCS and therefore both four priority rules could be used to schedule this kind of projects. Figure 6-4: Average deviation from optimum for th J60 set of projects. 0,00 2,00 4,00 6,00 8,00 10,00 12,00 14,00 1 GCRR LPF RSM GNIS GNS IRSM WCS ACS MinSlack LFT GCRR LPF RSM GNIS GNS IRSM WCS ACS MSLack LFT Average 6,95 5,52 12,89 11,63 6,74 8,82 5,87 5,60 5,52 6,21 6 Results and Conclusions 50 6.3 Results and conclusions for the J90 set of projects Table 6-5: Average deviation from optimum for different time windows J90 TW GCRR LPF RSM GNIS GNS IRSM WCS ACS MSLack LFT 0 5,88 5,46 7,22 9,34 6,09 6,98 5,76 5,96 5,46 5,40 1 5,86 5,08 8,24 10,16 5,86 7,40 5,51 5,69 5,08 5,04 2 6,43 5,65 10,64 11,65 6,40 8,11 6,04 6,04 5,65 5,71 3 7,31 6,13 13,55 13,61 7,36 9,25 6,36 6,39 6,13 6,53 4 8,35 6,62 16,71 15,02 8,16 10,12 6,94 6,75 6,62 7,29 5 8,73 7,11 20,02 16,56 8,84 11,22 7,29 7,19 7,11 8,05 6 9,10 7,34 22,37 17,74 9,24 11,99 7,49 7,43 7,34 8,70 7 9,35 7,42 24,24 18,36 9,49 12,18 7,78 7,46 7,42 9,00 8 9,55 7,54 25,05 18,44 9,69 12,07 7,99 7,47 7,54 9,17 9 9,53 7,40 24,25 19,08 9,90 12,42 7,87 7,39 7,40 9,30 Figure 6-5: Average deviation from optimum for different time windows J90 0,00 5,00 10,00 15,00 20,00 25,00 30,00 1 2 3 4 5 6 7 8 9 10 GCRR LPF RSM GNIS GNS IRSM WCS ACS MinSlack LFT 7.1 Introduction 57 7 Area Resource 7.1 Introduction As told in the chapter 2, a very important part of this document is the implementation of the Area Resource as an aditional resource constraint in the RCPSP. It involves an increase in the difficulty of the project solution but it also makes the scheduling problem to be more realistic and hence a better solution for the project manager can be reached. 7.2 Theory and explanation In a common project there are many different activities and all of them have different execution characteristics that had to be done in a proper way. Some of them do not need to be executed in an specific area such as for example the purchase of some construction tools but many others like the installation of a big hydraulic press in a firm must be done in the place where it should carry out its work or can be previously assembled anywhere and then transported to its working place by a big truck that would need a big amount of free area to go through. In all the literature read regarding the RCPSP, the usually resources taken into account are those related with workers, material, machines… However none of them are related with surface problems such as the previous problem of installation of a big press. Hence, this new resource tries to face common problems involving contruction projects or layout planning in most of the companies in which the availability of free area to execute a certain activity is of great importance. Not only for the cases studied before has the area resource been created but also for the scheduling of activities which need a constant delivery of resources. Therefore those activities will need a free path available in order to be possible to communicate them with the store and in this case the necessary area would not be where the activity is physically done but the area needed to go from the store to the place of execution of the activity. 7 Area Resource 58 As the reader could see, the new resource opens a wide variety of possible constraints in order to make the simulation of projects as real as possible to allow the project manager to decide the best way in scheduling the activities to reach the project objective in the best proper way. 7.3 Method applied In this document the case implemented with plant simulation is the one that refers to the area needed in the execution of an activity, like the hydraulic press commented in the chapter 6.2. 7.3.1 Requirements for the implementation In order to realize the simulation with the surface resource, some functions and agents have to be added to those explained in the chapter 4.4 related to the multiagent scheduling system. Thus, the resource agents related with the area as well as the necessity of surface where the process agent is going to be executed must be created. [Hor-12b] 7.3.2 Area´s resource agent To make possible the implementation of the different projects in the computer, a new resource pool has been created. This resource pool is supposed to represent the area where the project is going to be executed. This area has been created as a matrix in which the free positions are represented with a 0 and with a 1 the already used ones. This resource pool is composed of the new area agents which work as the resource agents explained in the chapter 4.4.2. The possible states of this new agents is also free, active and reserved. Each agent corresponds to a cell in the matrix previously explained. When a certain agent changes its state to active or reserved, the associated matrix will change the cell whose position this agent represent, from 0 to 1, number which means “not free”. Following the same process, when an agent gets the state free, the associated cell in the matrix will change to 0. [Hor-12c] 7.3 Method applied 59 7.3.3 Implementation Another matrix with the same dimensions has also been created for every activity but now the 1 represents the place where the activity should be carried out. The dimensions of the surface can be easily modified in the algorithm in order to provide the project manager a good tool to perform the most realistic scenario for his project. For the activities, as the tasks provided by the J30, J60, J90 and J120 test projects do not have this area resource it must also be created by the algorithm. The way of creating the necessary surface has been done as follows. Supposing the area of the project where is going to be executed as a matrix A(x,y) with x=y or not, the same matrix has been created for every activity. In order to delimitate the necessary area two different steps has been made. In the first step two integer variables have been calculated as normal functions with mean x/2 and y/2 and standadard deviation x/3 and y/3 respectively. After this calculation two positive values have been obtained and represent the “starting” point for the second step. In the second step two new integer variables have been created also with normal functions with mean 0 for both of them and standard deviation x/3 and y/3 respectively. Now the way of using this obtained values is as follows. Supposing that the values obtained in the first step are a and b, the point in the matrix A(a,b) would be the “starting” point of the necessary area. Thus A(a,b) will have now a value of 1 instead of 0. The net value of the variables calculated in the second step represent the x and y dimension of the area and the sign the direction. That means that if the value for the variables in the second step is -3 and 4 respectively starting in the point (a,b) the area for this activity is a 3 x 4 rectangle and the signus – represents that the area is occupied at the left of the x axe. In the studied example, the dimensions of the surface are 10 x 8 as can be sawn in the figure below. 7 Area Resource 60 Figure 7-1: Example area´s dimension Then for the first step the value assigned to the first variable will be a random value of a normal distribution with mean=10/2 and standard deviation 10/3 and for the second variable mean=8/2 and standard deviation 8/3. Supposiing that the values obtained are a=6 and b=4 the starting point of the matrix will be A(6, 4) and therefore the matrix now will be as shown in Figure 6-2. Figure 7-2: Result after first step In the second step, the mean now for both variables c and d is 0 and the standard deviation is 10/3 and 8/3 respectively. The values obtained now are c=-4 and d=3 and hence the necessary area is a 4 x 3 rectangle with the “starting” point (6,4) and the final result is as follows. 7.3 Method applied 61 Figure 7-3: Necessary area for the example activity. 7 Area Resource 62 7.3 Method applied 63 8 Conclusions The priority rule that has been selected to test the Area´s Resource is LPF due to the good results yielded. The way of proceeding has been the same as the one utilized in the chapter 5. The Area´s Resource has been tested also with the J30, J60, J90 and J120 set of projects. As the activities in this projects do not require the Area´s Resource, it has been created following the indications given in the chapter 6.3. For the J30, the algorithm has been executed for the 480 projects that it is composed of and has been repeated for the ten different values of time window. Altogether 4800 projects. The same procedure has been done with the J60 and J90 and finally with the J120, with the exception that the number of projects executed was 600 and then the sum of projects scheduled rises to 6000. As this resource has never been studied, there are no papers to compare the results and there are also no optimal solutions for the projects executed. The conclusions are then going to be based in the difference of the deviation from the optimum for the set of projects with and without the Area´s Resource. The tables used shows the average deviation from the optimum (mean), the total deviation from the optimum for the total amount of projects (sum) and the number of projects executed for every value of time window (NP). In the left part of the table, the results represented are those that correspond to the execution of the project with the Area´s Resource whereas in the right side of the table correspond to the results without the resource. 8 Conclusions 64 8.1 Results for the J30 set of projects Table 8-1: Results for the J30 with area TW Mean Sum NP Mean Sum NP 0 31,59 15163 480 3,02 1449 480 1 31,46 15100 480 2,91 1397 480 2 31,70 15215 480 3,14 1507 480 3 32,19 15453 480 3,26 1567 480 4 32,76 15723 480 3,44 1653 480 5 33,23 15949 480 3,67 1761 480 6 33,80 16225 480 3,93 1888 480 7 34,16 16399 480 4,04 1941 480 8 34,33 16480 480 4,10 1970 480 9 34,36 16491 480 4,10 1967 480 Figure 8-1: Chart for the J30 with area 0,00 5,00 10,00 15,00 20,00 25,00 30,00 35,00 40,00 0 1 2 3 4 5 6 7 8 9 With Surface Without Surface 8.2 Results for the J60 set of projects 65 Table 8-2: Rate for the J30 with area Mean with area Mean without area Rate 32,96 3,56 9,25 The rate is the result of dividing the mean with area by the mean without area. Represent the per unit deviation that the mean with area is bigger than without area. In this case, the rate is 9.25 and the deviation from optimum rises to 32.96 results that are clearly not good in comparison with the previously obtained. 8.2 Results for the J60 set of projects Table 8-3: Results for the J60 with area TW Mean Sum NP Mean Sum NP 0 70,03 33614 480 4,85 2327 480 1 69,93 33564 480 4,57 2195 480 2 70,83 33998 480 4,62 2216 480 3 71,90 34511 480 5,02 2408 480 4 73,28 35173 480 5,49 2635 480 5 74,56 35790 480 5,76 2765 480 6 75,48 36229 480 6,06 2911 480 7 76,38 36661 480 6,19 2970 480 8 76,64 36787 480 6,33 3036 480 9 76,86 36892 480 6,34 3044 480 8 Conclusions 66 Figure 8-2: Chart for the J60 with area Table 8-4: Rate for the J60 with area Mean with area Mean without area Rate 73,59 5,52 13,33 0,00 10,00 20,00 30,00 40,00 50,00 60,00 70,00 80,00 90,00 0 1 2 3 4 5 6 7 8 9 With Surface Without Surface 73 Bibliography [Ade-91] Adelsberger, H.; Kanet, J.: The leitstand- A new tool for computerintegrated manufacturing, Production and Inventory Management Journal volume 32, 1991. [Arc-08] Archer, S.: Stochastic Resource Constrained Project Scheduling with Stochastic Task Insertions Problems, Google Books, 2008. [Boc-90] Boctor, F.F.: Some efficient multi-heuristic procedures for resourceconstraint project scheduling. European Journal of Operations Management volume 49, 1990. [Bou-03] Bouleimen, K.; Lecocq, H.: A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, European Journal of Operations Management volume 149, 2003. [Cle-06] Clealand, D; Gareis, R.: Global Project Management Handbook, McGraw- Hill Professional, ISBN 0-07-146045-4, 2006. [Dav-75] Davis, E.W.; PattersonJ.H.: A comprasion of heuristics and optimum solutions in resource-constraint project scheduling, Management Science, 1975. [Hor-12a] Expert interview with Dipl.-Ing Tim Horenburg. Mai 2012. [Hor-12b] Expert interview with Dipl.-Ing Tim Horenburg. June 2012. [Hor-12c] Expert interview with Dipl.-Ing Tim Horenburg. August 2012. [Hor-12d] Horenburg, T.; Wimmer, J.; Günthner, W.A.: Resource Allocation in Construction Scheduling based on Multi-Agent Negotiation. Institute for Materials Handling, Material Flow, Logistics, Technische Universität München, 2012. 74 [Kol-96] Kolisch, R.: Efficient priority rules for the resource constrained projectscheduling problem, European Journal of Operations Management volume 14, 1996. [Kum-98] Kum-Khiong, Y.: A Comparison of Dispatching Rules for Executing a Resource-constrained Project with Estimated Activity Durations, European Journal of Operations Management volume 26, 1998. [McL-01] McLean, C.; Leong, S.: The Role of Simulation in Strategic Manufacturing, citeseerx, 2001 [Mer-12] Merriam-Webster: Simulation, 2012. URL: http://www.merriamwebster.com/dictionary/simulation. [PSim-10] Plant Simulation . Siemens PLM. 2010. [PSU-05a] The Pennsylvania State University: Project Constraints, 2005. URL https://courses.worldcampus.psu.edu/welcome/pmangt/samplecontent/5 20lesson08/lesson08_02.html. [PSU-05b] The Pennsylvania State University: Resource Constraints, 2005. URL https://courses.worldcampus.psu.edu/welcome/pmangt/samplecontent/5 20lesson08/lesson08_03.html. [Sim-96] Simpson, W.; Patterson, J.: A multiple-tree search procedure for the result-constrained project scheduling problem, European Journal of Operations Management volume 89, 1996. [Sta-93] Stadtler, H.; Wilhelm, S.: Einsatz von Fertigungsleitständen in der Industrie, CIM-Management Heft 1, 1993. [Sti-78] Stinson, J.; Davis, E; Khumawala, B: Multiple Resource–Constrained Scheduling Using Branch and Bound, Taylor & Francis online, 1978. [Sun-04] Sun, R.; Naveh, I.: Simulating Organizational Decision-Making Using a Cognitively Realistic Agent Model, Journal of Artificial Societies and Social Simulation volume 7, 2004. [Tob-91] Tobias, A.: O.R. techniques for use in redesigning manufacturing and associated business systems, European Journal of Operations Management 75 volume 51, 1991. [Val-01] Valls, V.; Ballestín, F.; Quintanilla, S.: An Evolutionary Approach to the Resource-Constraint Project Scheduling Problem, CiteseerX, 2001. [Val-08] Valls, V.; Ballestín, F.; Quintanilla, S.: A hybrid genetic algorithm for the resource-constraint project scheduling problem, European Journal of Operations Management volume 185, 2008. [Wan-06] Wang, T; Li, x; Wang, X.: Simulated Evolution and Learning, Springer, 2006. [Wit-03] Witzel, M.: Fifty key figures in management. Routledge, ISBN 0-415- 36977-0. Pag 96-101, 2003. [Yan-01] Yang, B.; Geunes, J.: Resource-Constrained Project Scheduling: Past Work and New Directions, citeseerx, 2001. [You-05] Young-Hoon, K.: A brief History of Project Management, In: The story of managing projects. Greenwood publishing group, ISBN 1-56720-506-2, 2005. 77 List of figures Figure 4-1: First project example 8 Figure 4-2: Project solution for the RSM priority rule 10 Figure 4-3: First solution for the IRSM priority rule 13 Figure 4-4: Second solution for the IRSM priority rule 13 Figure 4-5: Project solution for the MSLK priority rule 14 Figure 4-6: Project solution for the WCS priority rule 15 Figure 4-7: Project solution for the ACS priority rule 16 Figure 4-8: Project solution for the SPT priority rule 17 Figure 4-9: Project solution for the MAxDur priority rule 18 Figure 4-10: Project solutions for the GRD priority rule 19 Figure 4-11: Project solution for the MRR priority rule scheduling first activity 3 20 Figure 4-12: Project solution for the MRR priority rule scheduling first activity 4 20 Figure 4-13: Second project example 21 Figure 4-14: Project solution for the MinEFT priority rule 22 Figure 4-15: Project solution for the GCRR priority rule 24 Figure 4-16: Project solution for the GCRR priority rule 25 Figure 4-17: First solution for the GNS priority rule 26 Figure 4-18: Second solution for the GNS priority rule 26 Figure 4-19: Two possible solutions for the SNS priority rule 27 Figure 4-20: Project solution for the RPW priority rule 28 Figure 4-21: Project solution for the RPW priority rule 30 Figure 4-22: Project solutions for the GNIS priority rule 31 Figure 4-23: Two possible solutions for the SNIS priority rule 32 Figure 5-1: Different states of process agents [Hor-12d] 37 Figure 5-2: Multi-Agent system for project scheduling [Hor-12d] 38 Figure 5-3: Result´s comparison of the IRSM 40 Figure 6-1: Average deviation from optimum for different time windows, J30 44 Figure 6-2: Average deviation from optimum for th J30 set of projects. 46 Figure 6-3: Average deviation from optimum for different time windows, J60 47 Figure 6-4: Average deviation from optimum for th J60 set of projects. 49 Figure 6-5: Average deviation from optimum for different time windows J90 50 78 Figure 6-6: Average deviation from optimum for th J90 set of projects. 52 Figure 6-7: Average deviation from optimum for different time windows J120 53 Figure 6-8: Average deviation from optimum for th J120 set of projects. 55 Figure 6-9: Performance of priority rules [Kol-96] 56 Figure 7-1: Example area´s dimension 60 Figure 7-2: Result after first step 60 Figure 7-3: Necessary area for the example activity. 61 Figure 8-1: Chart for the J30 with area 64 Figure 8-2: Chart for the J60 with area 66 Figure 8-3: Chart for the J90 with area 67 Figure 8-4: Chart for the J90 with area 69 Figure 8-5: Rate for any set of projects 70 79 List of tables Table 4-1: RSM- Duration and Latest Start Time 9 Table 4-2: First iteration for the RSM priority rule 9 Table 4-3: Second iteration for the RSM priority rule 10 Table 4-4: First iteration for the IRSM priority rule 12 Table 4-5: Second iteration for the IRSM priority rule 12 Table 4-6: First iteration for the MSLK priority rule 14 Table 4-7: First iteration for the WCS priority rule 15 Table 4-8: First iteration for the ACS priority rule 16 Table 4-9: First iteration for the SPT priority rule 17 Table 4-10: First iteration for the MAxDur priority rule 18 Table 4-11: First iteration for the GRD priority rule 19 Table 4-12: First iteration for the MRR priority rule 20 Table 4-13: Duration and LST for the RSM priority rule 21 Table 4-14: First iteration for the MRR priority rule 22 Table 4-15: First iteration for the GCRR priority rule 23 Table 4-16: Second iteration for the GCRR priority rule 24 Table 4-17: First iteration for the GCRR priority rule 25 Table 4-18: First iteration for the GNS priority rule 26 Table 4-19: First iteration for the SNS priority rule 27 Table 4-20: First iteration for the RPW priority rule 28 Table 4-21: First iteration for the RPW priority rule 29 Table 4-22: Iteration for the GNIS priority rule 30 Table 4-23: Iteration for the GNIS priority rule 31 Table 6-1: Average deviation from optimum for different time windows, J30 43 Table 6-2: Average deviation from optimum over all time windows, J30 46 Table 6-3: Average deviation from optimum for different time windows, J60 47 Table 6-4: Average deviation from optimum J60 49 Table 6-5: Average deviation from optimum for different time windows J90 50 Table 6-6: Average deviation from optimum J90 52 Table 6-7: Average deviation from optimum for different time windows J120 53 Table 6-8: Average deviation from optimum J120 54 80 Table 8-1: Results for the J30 with area 64 Table 8-2: Rate for the J30 with area 65 Table 8-3: Results for the J60 with area 65 Table 8-4: Rate for the J60 with area 66 Table 8-5: Results for the J90 with area 67 Table 8-6: Rate for the J60 with area 68 Table 8-7: Results for the J120 with area 68 Table 8-8: Rate for the J120 with area 69 1 Appendix A 1. Simluations As far as not every single details can be quoted in this document, a copy of the files used for this simulation is attached In the CD-ROM. The complete tables obtained in the simulations are attached as well. 2 Sworn Declaration I hereby declare to have made the present work independently and without assistance from third parties. Thoughts and quotes that I have taken from other sources directly or indirectly are identified as such. I hereby agree that the work can be made available to the public through the department Fördertechnik Materialfluss Logistik from the Technische Universität München, Germany as well as through the Universidad de Zaragoza, Spain. München, 1 November 2012 Fernando Alastuey González