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.