My research on Evolutionary Algorithms for Project Scheduling (Part I)

Hi there,

While working on my PhD, mainly focused on the Scheduling domain, specifically on the Resource Leveling (RLP) technique, I realized that there’s a lack of online resources on the RLP technique. I’ll try to share some of the online resources I’ve found. First of all, some words about my current research activity:

I’m currently working in solving an ad hoc combination of RCPSP (Resource constrained Scheduling problem) and RLP (resource leveling problem). In this problem (denominated eRLP, the Extended RLP) I also consider specific “work ranges” for each resource (a workrange is a time interval where the resource leveling is evaluated), thus, my goal is to optimize the balance on the resource usage of each heterogeneous resource (i.e. K resources) and the global makespan (duration) of the project. Hence, the eRLP minimizes K+1 -possible contradictory- objectives at the same time.

The workranges can be Full, Effective and Dynamic, to better illustrate these ranges:

eRLP Ranges

eRLP Ranges

– The full range refers to a time interval that considers the entire duration of a project, hence, the resource usage profile of a resource is calculated on the interval [Start of Project, End of Project]. This is the traditional case analyzed by the RLP. As an example, we can find this range in real life staffing/manpower scenarios where an employee has a fixed duration contract for the entire duration of the project.

– The dynamic range considers the time interval starting on the first resource usage and ending on the last resource usage. The resource usage profile for this range is calculated on the interval [Start time of first activity, End time of last activity]. As an example, consider the case of consultants with a contract that considers a specific workload and a continuous time period which depends on when the consultant starts and finish his/her duties and which is smaller than the total project duration.

– The effective range considers a set of –possibly discontinuous- time intervals where the resource has been used (i.e. resource usage is greater than 0). The resource usage profile for this range is calculated on this set of intervals. As an example, consider the case of external staff that is hired for multiple specific short-duration tasks.

In the eRLP, the resources are limited (in the traditional RLP the resources are unlimited).

So, the basic idea in my research is to solve the eRLP (optimize resource usage and makespan).
The “traditional” techniques (MOM, PACK, etc) WILL NOT solve this kind of problem. In fact, I found that my solver can solve problems with limited and unlimited resources as well in a competitive way to the alternative methods.

In my next post I’ll publish how I tackled this problem, which is basically a Evolutionary Algorithm.

Advertisements

5 Comments

  1. nicasso said,

    March 29, 2009 at 4:02 pm

    que tal la latencia del invento??? (lactancia) en el argod de los musicos xD
    Estoy deseando que pase el fin de semana para poder hacerme con los cables, el que parece que me va a dar mas problemas es el minijack de 4 pines con salida av rca. Creo que ipod tiene ese cable, mañana me pongo de lleno
    Lo consegui rular en mi slim gracias a una aplicacion llamada eloader. Subiré un video a youtube
    GuitarBox la alternativa a los alessis, pod , guitar rig y todos esos xD

  2. hosssein said,

    May 14, 2009 at 5:18 pm

    I am a researcher in resource leveling field. May I have your test set ? If yes please send me an email.

    • rocamatics said,

      May 15, 2009 at 6:09 pm

      Hello Hossein:

      I’m pleased to meet somebody who is also interested in multi resource leveling!! Of course I’d like to share my results and experiments with the community.

      You can get the test Suite from:
      http://www.adrive.com/public/cb2fbe1348e5448bbd9de6f9688f5f2d1819c52b820bad101bce8ec5901e5a96.html

      This is a benchmark suite of synthetic instances for the simultaneous resource leveling of multiple resources AND the minimization of the project duration (makespan) (The ERLP problem http://www.waset.org/ijci/v4/v4-4-38.pdf ).

      The files are in the .rcp file format (RCPSP instances, the same format specified in the PSPLIB library in http://129.187.106.231/psplib/ ). The name of the instance indicate the number of activities, the number of resources, and the problem type.

      Ex.

      ERLP_15_3 = RCPSP Instance with 15 activities and 3 resources (Single Solution)
      ERLP_15_3M = RCPSP Instance with 15 activities and 3 resources (Multi Solution)

      I’ve developed an instance viewer/solver for the RCPSP (including the source code), you can grab a copy at http://sourceforge.net/projects/pspsolver/

      Please remark that this benchmark considers the concept of WORKRANGE to evaluate the resource usage of the resources (please refer to the previous paper reference).
      The workrange of the resources is (in this sequence):

      m resources of type full,
      m resources of type dynamic,
      m resources of type effective

      Where m = NumberOfResources/3.

      There are two basic groups of instances:

      1) Single Solution: Instances where there exist an “IDEAL” solution (i.e. a solution that minimizes the fluctuation of the usage of all the resources and minimizes the makespan of the project).

      Ex. If you have a project Project_1 with 3 resources then there’s a single schedule S where

      rl(S, Resource_1) == 0 and rl(S, Resource_2) == 0
      and rl(S, Resource_3) == 0 and makespan(S)==minMakespan(Project_1)

      where:
      rl(s, x) = the resource leveling measure of resource x (i used the RLI, check my paper);
      makespan(s) = the makespan of schedule s;
      minMakespan(p) = the minimal makespan of project p*

      2) Multi Solution: Instances where there exist an optimal solution for EACH individual resource (zero fluctuation on the individual resource usage), and also there is an optimal solution (minimal makespan) for the project.

      Ex. If you have a project Project_1 with 3 resources then there’s 4 (NumberOfResources+1) schedules Si where

      rl(S1, Resource_1) == 0 and rl(S2, Resource_2) == 0
      and rl(S3, Resource_3) == 0 and makespan(S4)==minMakespan(Project_1)

      where:
      rl(s, x) = the resource leveling measure of resource x (i used the RLI, check my paper);
      makespan(s) = the makespan of schedule s;
      minMakespan(p) = the minimal makespan of the project p*

      * minMakespan(p) = (n\9)*6 + ((n%9)\6)*3 + ((n%9)%6)\3 where n = NumberOfActivities of project p, % = modulo op, \ = integer division.
      Ex. minMakesPan(ERLP_15_3) = 9;

      Of course, it could be relatively easy to find EACH optimal individual solution! However, the goal is the multiobjective optimization (simulateously, finding the best tradeoffs between each objective, refer to my paper for more details). These tradeoffs are the pareto fronts found by a solver. Please post again if you need the pareto fronts found by my solver).

      Regards,

      • Kim said,

        October 17, 2013 at 9:40 am

        Hello,
        Some of the links you mentioned in your previous comment seem to be broken now. Can you update them (the link to your solver works fine though).
        By the way, I am also a researcher in the RCPSP and found your work really interesting…

  3. Yep said,

    January 1, 2011 at 7:41 pm

    Hola Rocamatics… bueno yo soy nuevo en esto del psp, tengo apenas 6 meses de haber comprado el mío, pero desde entonces ví tu aplicación ya que soy un gran fanático de la guitarra y he esperado hasta que mi psp pudiera correr hombrews para utilizar el GuitarBox… y hace poco salío el Hen 6.20 B, yo creía que podía usar tu aplicación pero lamentablemente no he podido, jajajaja estoy un poco triste porque practicamente utilizaría mi psp con mi guitarra, (SERÍA LO MÁXIMO POR CIERTO) jajaja pero lamentablemente crashea…. mi pregunta es si puedes explicarme como puedo hacer para que funcione o saber si estas trabajando en una versión que se sea compatible con el Hen 6.20 o algo así, bueno solamente tengo esa duda y a la vez felicitarte por tan excelente aplicación (aunque solo la he visto por youtube jajajaj) ojalá alguien encuentre una solución… gracias


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: