Project scheduling and Solver Foundation revisited, Part IV

In previous posts in this series I described a mixed-integer programming model for resource constrained project scheduling, introduced some project data structures, and wrote a class that encapsulates Solver Foundation code to create and solve the model. Now let’s tie it all together with a short sample program to try it out. First, let’s write a function to generate a random project. CreateProject takes as input a task count and resource count. The specified number of resources are created (all with 100% availability). Then the specified number of tasks are created. Each task has one resource assignment. We cycle through the resources one at a time, and we randomly generate a task duration. Then, we create a few links between the tasks. We don’t do this completely at random, since that may generate a cycle between tasks: we wouldn’t want both a link A –> B and B->A. So we take care always to have links going from lower-numbered tasks to higher-numbered tasks. You can modify this function to generate more interesting random projects if you like.

  class ProjectUtilities {
    // (Replace this with code that creates a "real" project. This project is randomly generated.)
    public static Project CreateProject(int taskCount, int resourceCount) {
      System.Random random = new Random(0);
      int maxDuration = 5;
      int linkCount = Math.Max(taskCount / 5, 1);

      Resource[] resources = new Resource[resourceCount];
      for (int i = 0; i < resources.Length; i++) {
        resources[i] = new Resource("R" + i, 1.0);
      }

      Task[] tasks = new Task[taskCount];
      for (int i = 0; i < tasks.Length; i++) {
        tasks[i] = new Task("t" + i, random.Next(1, maxDuration + 1), new Assignment[] { new Assignment(resources[i % resources.Length], 1.0) });
      }

      TaskDependency[] links = new TaskDependency[linkCount];
      for (int i = 0; i < links.Length; i++) {
        int source = random.Next(0, taskCount - 1);
        int dest = random.Next(source + 1, taskCount); // guaranteeing no cycles.
        links[i] = new TaskDependency { Source = tasks, Destination = tasks[dest] };
      }

      return new Project(tasks, resources, links);
    }
}

Looking at the SchedulingModel.Solve() method from last time, we see that it returns a dictionary that maps task IDs to start times. Let’s write a method that prints out the schedule in an easy-to-read format. PrintProjectSchedule prints the ID, start, and finish for each task.

    public static void PrintProjectSchedule(Project project, IDictionary<int, double> schedule) {
      Console.WriteLine();
      Console.WriteLine("SCHEDULE:");
      foreach (var taskSchedule in schedule) {
        Task task = project.Tasks[taskSchedule.Key];
        double start = Math.Round(taskSchedule.Value, 3);
        Console.WriteLine("{0}: [{1} - {2}]", task.ID, start, start + task.Duration);
      }
    }

The last thing I would like to do is to be able to export my schedule to Microsoft Project. To do this, I can write out the schedule in CSV (comma separated) format, and import into Microsoft Project. Microsoft Project’s CSV format is very easy to figure out – just open Project, and use “Save As” to save a project as CSV (go here for more). Stare at it for a bit and you will get an idea. The only trick is that we need to convert our start and finish times from doubles to DateTimes. We will interpret the doubles as representing the number of working days since the start of the project. Most people work Monday through Friday, so in order to do this conversion we will have to skip weekends. Also we want to honor the standard working hours of 8AM – 5PM. To pull this off I will introduce two more utility routines. If you don’t care about Microsoft Project, you can just copy the code and move on

    private static DateTime AddDays(DateTime start, double days, bool isStart) {
      while (days > 0) {
        if (days > 1) {
          start = start.AddDays(1);
          start = NextWorkingTime(start, false);
          days -= 1.0;
        }
        else {
          start = start.AddHours(9 * days);
          if (start.TimeOfDay >= TimeSpan.FromHours(isStart ? 17 : 17.01)) {
            TimeSpan duration = start.TimeOfDay - TimeSpan.FromHours(17);
            start = NextWorkingTime(start, isStart).Add(duration);
          }
          days = 0;
        }
      }
      start = NextWorkingTime(start, isStart);
      return start;
    }

    private static DateTime NextWorkingTime(DateTime start, bool isStart) {
      if (start.TimeOfDay >= TimeSpan.FromHours(isStart ? 17 : 17.01)) {
        start = start.Date.AddHours(24 + 8);
      }
      else if (start.Hour < 8) {
        start = start.Date.AddHours(8);
      }

      while (start.DayOfWeek == DayOfWeek.Saturday || start.DayOfWeek == DayOfWeek.Sunday) {
        start = start.AddDays(1);
      }
      return start;
    }

    public static string ToCsv(Project project, IDictionary<int, double> schedule) {
      DateTime projectStart = new DateTime(2011, 2, 1, 8, 0, 0);
      StringBuilder build = new StringBuilder(40 + project.Tasks.Count * 30);
      build.AppendLine("ID,Name,Duration,Start_Date,Finish_Date,Predecessors,Resource_Names");
      Dictionary<string, int[]> depMap = project.Dependencies
        .GroupBy(d => d.Destination.Name)
        .ToDictionary(g => g.Key, g => g.Select(d => d.Source.ID + 1).ToArray()); // need to add 1 for MS Project.
      foreach (Task task in project.Tasks) {
        string predNames = "";
        int[] predIds = null;
        if (depMap.TryGetValue(task.Name, out predIds)) {
          predNames = "\"" + string.Join(",", predIds) + "\"";
        }
        string resourceNames = "\"" + string.Join(",", task.Assignments.Select(a => a.Resource.Name)) + "\"";
        double startDay = schedule[task.ID];
        DateTime start = AddDays(projectStart, startDay, true);
        DateTime finish = AddDays(start, task.Duration, false);
        build.AppendFormat("{0},{1},{2}d,{3},{4},{5},{6}", task.ID + 1, task.Name, task.Duration,
          start, finish, predNames, resourceNames);
        build.AppendLine();
      }
      return build.ToString();
    }
  }

We’re almost done. All we need now is a Main() routine that creates a project, solves it, and prints out the results. Here goes:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace ProjectScheduling {
  /// <summary>Driver.
  /// </summary>
  class Program {
    static void Main(string[] args) {
      int taskCount = args.Length > 0 ? Int32.Parse(args[0]) : 5;
      int resourceCount = args.Length > 1 ? Int32.Parse(args[1]) : 2;
      bool verbose = (args.Length > 2 ? Int32.Parse(args[2]) : 0) != 0;

      Project project = ProjectUtilities.CreateProject(taskCount, resourceCount);
      Console.WriteLine(project);

      Stopwatch stopwatch = new Stopwatch();
      SchedulingModel m = new SchedulingModel(verbose);

      stopwatch.Start();
      m.Initialize(project);
      Console.WriteLine("Init time = " + stopwatch.Elapsed);
      IDictionary<int, double> schedule = m.Solve();
      Console.WriteLine("Total time = " + stopwatch.Elapsed);

      ProjectUtilities.PrintProjectSchedule(project, schedule);
      Console.WriteLine(ProjectUtilities.ToCsv(project, schedule));
    }
  }
}

As you can see, you can supply the task count, resource count, and whether to print debug output through the command line. Here is the output for “schedulingmodel 5 2”:

----------------------------------------
PROJECT
TASKS
0: t0 duration = 4
1: t1 duration = 5
2: t2 duration = 4
3: t3 duration = 3
4: t4 duration = 2
LINKS
2 -> 4
RESOURCES
0: R0 max units = 1
1: R1 max units = 1
----------------------------------------

Init time = 00:00:00.2296806
Total time = 00:00:00.8855667

SCHEDULE:
0: [0 - 4]
1: [0 - 5]
2: [4 - 8]
3: [5 - 8]
4: [8 - 10]
ID,Name,Duration,Start_Date,Finish_Date,Predecessors,Resource_Names
1,t0,4d,2/1/2011 8:00:00 AM,2/4/2011 5:00:00 PM,,"R0"
2,t1,5d,2/1/2011 8:00:00 AM,2/7/2011 5:00:00 PM,,"R1"
3,t2,4d,2/7/2011 8:00:00 AM,2/10/2011 5:00:00 PM,,"R0"
4,t3,3d,2/8/2011 8:00:00 AM,2/10/2011 5:00:00 PM,,"R1"
5,t4,2d,2/11/2011 8:00:00 AM,2/14/2011 5:00:00 PM,"3","R0"

The nice thing is that you can copy and paste the bottom part of this output into a CSV file and then view the results in Project.

One last important point. If you enable the debug switch and examine the output from the Gurobi solver, you will notice that typically the solver is able to get a pretty good solution relatively quickly, and then spends a long time proving that the solution is optimal. Here is a typical output log: notice that the incumbent solution goes down to 41 days in only 4 seconds, even though the run takes over 30 seconds.

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Tim

     0     0    0.02924    0  227   48.00000    0.02924   100%     -    0s
H    0     0                      47.0000000    0.02924   100%     -    0s
     0     0    0.17738    0  167   47.00000    0.17738   100%     -    0s
     0     0    0.17835    0  174   47.00000    0.17835   100%     -    0s
     0     0    0.18278    0  168   47.00000    0.18278   100%     -    1s
     0     0    0.18509    0  170   47.00000    0.18509   100%     -    1s
H    0     0                      44.0000000    0.18509   100%     -    1s
     0     0    0.22003    0  246   44.00000    0.22003  99.5%     -    1s
     0     0    0.22474    0  254   44.00000    0.22474  99.5%     -    1s
     0     0    0.22670    0  258   44.00000    0.22670  99.5%     -    1s
     0     0    0.22670    0  267   44.00000    0.22670  99.5%     -    1s
     0     0    0.26301    0  233   44.00000    0.26301  99.4%     -    2s
H    0     0                      42.0000000    0.26301  99.4%     -    2s
     0     0    0.26435    0  262   42.00000    0.26435  99.4%     -    2s
H    0     0                      41.0000000    0.26435  99.4%     -    2s
     0     0    0.26440    0  283   41.00000    0.26440  99.4%     -    2s
     0     0    0.26646    0  272   41.00000    0.26646  99.4%     -    2s
     0     0    0.26695    0  269   41.00000    0.26695  99.3%     -    3s
     0     0    0.26695    0  288   41.00000    0.26695  99.3%     -    3s
     0     0    0.28377    0  314   41.00000    0.28377  99.3%     -    3s
     0     0    0.28476    0  329   41.00000    0.28476  99.3%     -    3s
     0     0    0.28476    0  336   41.00000    0.28476  99.3%     -    3s
     0     0    0.28476    0  276   41.00000    0.28476  99.3%     -    4s
     0     0    0.28476    0  289   41.00000    0.28476  99.3%     -    4s
     0     0    0.28476    0  296   41.00000    0.28476  99.3%     -    4s
     0     0    0.28476    0  260   41.00000    0.28476  99.3%     -    4s
     0     2    0.28476    0  260   41.00000    0.28476  99.3%     -    5s
H   59    39                      40.0000000    0.96732  97.6%  37.9    6s
   822   556    1.50000   16  317   40.00000    1.00000  97.5%  14.4   10s
   884   598    1.66667   24   84   40.00000    1.00000  97.5%  26.2   15s
  1377   841   12.35714   69   39   40.00000    1.00000  97.5%  24.4   20s
  2308  1201   11.00000   44   40   40.00000    1.00000  97.5%  21.2   25s
  2900  1531   15.00000   60   32   40.00000    1.00000  97.5%  18.9   30s

 

You can use the properties on GurobiDirective to terminate earlier if you want. For example, if I want to solve for at most 30 seconds, I can change the first part of Solve() to:

      GurobiDirective directive = new GurobiDirective();
      directive.OutputFlag = verbose;
      directive.TimeLimit = (int)TimeSpan.FromSeconds(30).TotalMilliseconds;

GurobiDirective has lots of options for controlling the solver behavior: check the documentation for details.

Project scheduling and Solver Foundation revisited, Part III

It’s time to get down to business and write a SchedulingModel class that encapsulates the resource constrained project scheduling model I wrote about in my previous two posts. Let’s break it down into three phases: defining the state, writing the code that constructs the model, and writing a function that solves the model and returns the results. To define the state, let’s review the important data associated with the model:

• Each event has a start date (t). We’ll call this Decision start.
• Each task is either active or inactive for each event (z). Let’s call this Decision isActive.
• The project duration is represented by C_max. We’ll call this makespan.
• The duration of each task (p) is an input Parameter.
• The above Decisions and Parameters are indexed by the sets of tasks and events.

We will have private member fields for this information since they will be used by the model throughout. Here is the start of our SchedulingModel class:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using Microsoft.SolverFoundation.Common;
using Microsoft.SolverFoundation.Services;
using SolverFoundation.Plugin.Gurobi;

namespace ProjectScheduling {
  /// <summary>A Solver Foundation model for solving resource constrained project scheduling problems.
  /// </summary>
  /// <remarks>
  /// This model produces a schedule with minimum duration with no overallocations.
  /// 
  /// The source for this model is:
  /// "Event-based MILP models for resource-constrained project scheduling problems"
  /// by Oumar Kone, Christian Artigues, Pierre Lopez, Marcel Mongeau in
  /// Computers and Operations Research, December 2009. This model is the "On/Off Event-Based Formulation"
  /// presented in section 3.2.
  /// </remarks>
  public class SchedulingModel {
    private bool verbose;
    private SolverContext context;
    private Model model;
    private Set tasks, events, events1ToN; // in the paper: sets A, R, E, and E - 0.
    private Decision makespan; // C_max
    private Decision isActive; // z
    private Decision start; // t
    private Parameter duration; // p

    /// <summary>Create a new instance.
    /// </summary>
    /// <param name="verbose">Indicates whether to dump intermediate output.</param>
    public SchedulingModel(bool verbose) {
      this.verbose = verbose;
    }

    /// <summary>Create the model.
    /// </summary>
    /// <param name="project">The project to be scheduled.</param>
    public void Initialize(Project project) {
      context = SolverContext.GetContext();
      context.ClearModel();
      model = context.CreateModel();

      int eventCount = project.Tasks.Count;

      // we will fill these in in the remainder of the post.
      InitializeSets(project.Tasks.Count, eventCount, project.Resources.Count);
      InitializeParameters(project.Tasks, project.Resources);
      InitializeDecisions();
      InitializeGoal();
      InitializeConstraints(project, eventCount);
    }
}

 

Now let’s do the important part: write the model.  This amounts to transcribing equations (34) – (45) on Page 9 of the paper. You might find the remainder of the post easier to follow if you have the paper with you as you read through the code and descriptions. The first thing I like to do is think about the Sets, Parameters (inputs) and Decisions (outputs) I will need, and then write down the constraints and goals. Let’s start with Sets. Looking over the equations we can observe the following:

• Most of the equations involve a “foreach” over the set E of events or the set A of tasks (or both). In these cases we will want to use the Model.Foreach construct.
• Equations (39) – (43) use summations. The natural SFS construct to use is Model.Sum. But note some subtle variations:
  • In equation (39) we sum over the events from 0 to e-1, where e itself can be any event from 1 to Events.Count. The summations in (40) and (42) similar structure.
  • The summation in (41) is simple: sum over all events.
  • (43) appears simple: we just sum from i = 0 to n – 1.

If you review the documentation for Model.Sum you will see that the first argument is a Set, and the second is a Func that maps a Term (which represents an element of the set) to a Term (which represents the operand to Sum). This means that it won’t work too well for the sums in equations (39), (40), (42) because the number of terms in the sum varies depending on the value of e. We can still do what we want by just computing the sum ourselves using a standard C# for-loop. Therefore we need three sets: the set of tasks, the set of events, and the set of events from 1 to n. There are two ways to establish the elements of a Set. The first works for the case where the elements are numeric: specify the start, end, and step. I will use this constructor for the event-based sets. The second is more commonly used: define a Parameter or Decision that uses the Set, and bind the Parameter or Decision to a data source using SetBinding. The elements of the Set will be determined automatically. I like this way of defining sets because it is less brittle: if the size of my problem changes I generally don’t need to touch my code. I will use this for the task set, since I know I need to bind the task duration to a Parameter.

    private void InitializeSets(int taskCount, int eventCount, int resourceCount) {
      tasks = new Set(Domain.Real, "tasks");
      events = new Set(0, eventCount, 1);
      events1ToN = new Set(1, eventCount, 1); // starting from event 1.
    }

 

Next come Parameters. You can identify these by looking at the “input variables” of the equations. Here they are p_I (the task duration), b_ik (amount of work on task I performed by resource k) and B_k (resource availability). B_k and b_ik appear in equation (43). Stare at it for a second, and think about the data structures we defined last time. We defined an Assignment class that represents work performed by a resource on a task. Each task has a list of assignments. Therefore we do not really have a matrix b_ik, at least not in a single collection. We’ll need to iterate over the assignments for each task to collect the resource usage and capacity – so it doesn’t really buy us anything to define Parameters for these quantities. So we’ll just define a parameter for task duration – and remember that this will also establish the elements of the tasks set we defined earlier.

    private void InitializeParameters(ICollection<Task> t, ICollection<Resource> r) {
      duration = new Parameter(Domain.RealNonnegative, "duration", tasks);
      duration.SetBinding(t, "Duration", "ID");
      model.AddParameters(duration);
    }

 

Now for the Decisions. Those come straight out of the paper. When we define the decisions we need to specify the Sets over which they are indexed, and the range of possible values (the Domain) for each.

    private void InitializeDecisions() {
      makespan = new Decision(Domain.RealNonnegative, "makespan");
      isActive = new Decision(Domain.IntegerRange(0, 1), "isActive", tasks, events);
      start = new Decision(Domain.RealNonnegative, "start", events);
      model.AddDecisions(makespan, isActive, start);
    }

 

The Goal is incredibly simple: minimize the makespan.

    private void InitializeGoal() {
      Goal goal = model.AddGoal("goal", GoalKind.Minimize, makespan); // (34)
    }

 

Now the fun part: the constraints. Of course, we have already examined most of the constraints so that we could define the other parts of our model. This is not unusual! Let’s work from top to bottom, starting with (35).  This constraint establishes the makespan for the project: the latest finish time for any task. The equation says the constraint holds for all events and tasks, but that isn’t quite true: notice that we compare the start of event e with the start of event (e-1). So we actually want to start from event 1.

    private void InitializeConstraints(Project project, int eventCount) {
      // Establish the makespan: the maximum finish time over all activities.
      model.AddConstraint("c35",
        Model.ForEach(events1ToN, e =>
          Model.ForEach(tasks, i =>
            makespan >= start[e] + (isActive[i, e] - isActive[i, e - 1]) * duration[i]
      )));

 

(36) is trivial:

      // The first event starts at time 0.
      model.AddConstraint("c_36", start[0] == 0);

 

(37) is a foreach over each task and unique pair of events. It relates the isActive and start decisions. To model the fact that we want to consider unique pairs, we place a ForeachWhere inside a ForEach. The condition on the ForeachWhere ensures that the inner event index f exceeds outer event index e.

      // Link the isActive decision to the starts of each event and task durations.
      model.AddConstraint("c_37",
        Model.ForEach(events1ToN, e =>
          Model.ForEachWhere(events, f =>
            Model.ForEach(tasks, i =>
              start[f] >= start[e] + ((isActive[i, e] - isActive[i, e - 1]) - (isActive[i, f] - isActive[i, f - 1]) - 1) * duration[i]
              ), f => f > e)));

 

As I alluded to in my first post, the original paper does not consider the first event, so let us add one more constraint (37a).

      // Link the isActive decision with the first event. This constraint is missing in the original
      // paper.
      model.AddConstraint("c_37_e0",
        Model.ForEach(events1ToN, f =>
          Model.ForEach(tasks, i =>
            start[f] >= start[0] + (isActive[i, 0] - (isActive[i, f] - isActive[i, f - 1]) - 1) * duration[i]
        )));

 

(38) is easy.

      // Order the events.
      model.AddConstraint("c_38", Model.ForEach(events1ToN, e => start[e] >= start[e - 1]));

 

(39) and (40) are very similar, so let’s focus on (39). We looked at these when we were figuring out which Sets to define. Since the sum ranges from event 0 to event e, where e varies, we decided to use nested for-loops instead of the Model.Foreach construct. The outer loop is over the event e. If we look at the summation, we sum over events 0 .. e-1. We will use the SumTermBuilder class to accumulate these terms (I blogged about this class awhile ago – it is part of Solver Foundation 3.0).

      // Ensure adjacency of events for an in-progress task.
      SumTermBuilder sum = new SumTermBuilder(eventCount);
      for (int i = 0; i < project.Tasks.Count; i++) {
        for (int e = 1; e < eventCount; e++) {
          sum.Add(isActive[i, e - 1]);
          model.AddConstraint("c_39_" + i + "_" + e,
            sum.ToTerm() <= e * (1 - (isActive[i, e] - isActive[i, e - 1])));
        }
        sum.Clear();
      }

      sum = new SumTermBuilder(eventCount);
      for (int i = 0; i < project.Tasks.Count; i++) {
        for (int e = 1; e < eventCount; e++) {
          for (int e1 = e; e1 < eventCount; e1++) {
            sum.Add(isActive[i, e1]); // (it's inefficient to reconstruct this for each value of e.)
          }
          model.AddConstraint("c_40_" + i + "_" + e,
            sum.ToTerm() <= e * (1 + (isActive[i, e] - isActive[i, e - 1])));
          sum.Clear();
        }
      }

 

(41) is easy.

      // All activities must be active during the project.
      model.AddConstraint("c_41", Model.ForEach(tasks, i =>
        Model.Sum(Model.ForEach(events, e => isActive[i, e])) >= 1));

 

(42) is not too hard at this point either. We need to iterate over the set of task dependencies, and add a constraint involving a summation for each. We once again use the SumTermBuilder class for performance.

      // A link (i, j) means that the start of task j must be after the finish of task i.
      int c42 = 0;
      foreach (TaskDependency link in project.Dependencies) {
        int i = link.Source.ID;
        int j = link.Destination.ID;
        sum = new SumTermBuilder(eventCount);
        for (int e = 0; e < eventCount; e++) {
          sum.Add(isActive[j, e]); // sum now has isActive[j, 0] .. isActive[j, e].
          model.AddConstraint("c_42_" + c42++, isActive[i, e] + sum.ToTerm() <= 1 + e * (1 - isActive[i, e]));
        }
      }

 

(43) is the last constraint – we already took care of (44) and (45) in our Decision definitions. We considered this constraint in some detail when we were figuring out our Parameter definitions. We want to express the fact that the sum of resource work on all tasks is no greater than its availability. This condition needs to hold for each event. The key is to iterate over all the assignments for all the tasks, and group the b_ik * z_ie terms by resource, using a Dictionary. Since most resources only work on a small percentage of the tasks, there will be very few nonzero b_ik terms. If we had stored the b_ik in a sparse matrix, this constraint would have been easier to write, on the other hand this would be more inconvenient in other parts of the system.

      // Resource usage during each event must not exceed resource capacity.
      Dictionary<Resource, int> resToId = new Dictionary<Resource, int>(project.Resources.Count);
      for (int k = 0; k < project.Resources.Count; k++) {
        resToId[project.Resources[k]] = k;
      }
      SumTermBuilder[] totalResWork = new SumTermBuilder[project.Resources.Count];
      int c43 = 0;
      for (int e = 0; e < eventCount; e++) {
        for (int taskID = 0; taskID < project.Tasks.Count; taskID++) {
          foreach (var assn in project.Tasks[taskID].Assignments) {
            int resID = resToId[assn.Resource];
            if (totalResWork[resID] == null) {
              totalResWork[resID] = new SumTermBuilder(4); // most tasks will have <= 4 assignments.
            }
            totalResWork[resID].Add(assn.Units * isActive[taskID, e]);
          }
        }

        for (int resID = 0; resID < totalResWork.Length; resID++) {
          if (totalResWork[resID] != null) {
            model.AddConstraint("c43_" + c43++, totalResWork[resID].ToTerm() <= project.Resources[resID].MaxUnits);
            totalResWork[resID] = null; // note: memory churn...
          }
        }
      }

 

Whew. The rest is easy. We will expose a wrapper for SolverContext.Solve(). The return type for this function is a dictionary that maps task IDs to scheduled start date. We use a LINQ query to produce this dictionary from the Solver Foundation results.

    /// <summary>Solve the model.
    /// </summary>
    public IDictionary<int, double> Solve() {
      GurobiDirective directive = new GurobiDirective();
      directive.OutputFlag = verbose;
      //SimplexDirective directive = new SimplexDirective(); // use me if you do not have Gurobi.
      var solution = context.Solve(directive);
      if (verbose) {
        Console.WriteLine(solution.GetReport());
      }

      return GetStartTimesByTask();
    }

    private IDictionary<int, double> GetStartTimesByTask() {
      // The "start" decision has the start times for each *event*. Index 0 has the start and index 1 has the event.
      // Recall that the event set was created using Rationals, so we must convert to int here.
      var eventToStart = start.GetValues().ToDictionary(o => (int)((Rational)o[1]).ToDouble(), o => (double)o[0]);

      // Group the isActive decision by task.
      var isActiveByTask = isActive.GetValues().GroupBy(o => o[1]);

      // Find the first event where each task is active, and transform the output into (task, event) pairs.
      var firstActiveByTask = isActiveByTask
        .Select(g => g.First(a => (double)a[0] > 0.5))
        .Select(o => new { TaskID = (int)((double)o[1]), EventID = (int)((Rational)o[2]).ToDouble() });

      // Now we can use the (task, event) pairs to get a dictionary that maps task IDs to start dates.
      return firstActiveByTask.ToDictionary(f => f.TaskID, f => eventToStart[f.EventID]);
    }
  }

 

That’s a lot of code and it’s possible (perhaps probable) that I have made a mistake. So in the next post I will write a simple test program to see how it works.

Project scheduling and Solver Foundation revisited, Part II

My current series is focused on building a Solver Foundation model for resource constrained project scheduling. I’m trying to walk the fine line between taking on too much (which might result in obscuring the main ideas…and making me work too hard), and taking on too little (which might result in a bit of toy code of no use to anyone). By choosing the event-based model described last time, I hope that the model itself is a good starting point for real world use. My other concern has to do with the implementation itself. I am not going to attempt to write production quality code, but I am going to try and provide sensible structure. To that end, I am going to separate the code that describes the data (the project, its tasks, assignments, and resources) from the model itself. No crap about Solver Foundation in the container classes, and no crap about data structures in the modeling code.

So let’s write up some simple classes to represent the entities we’ll need to work with. The most important entities are tasks and resources. A task is an activity that needs to be completed. The main things we want to know about a task are: when does it start? when does it end? how long does it take? A resource is something that can work on a task – it can be a “work resource” (such as an employee), or a “material resource” (e.g. a machine). The main thing we want to know about a resource is its capacity to complete tasks. The association of a particular resource to a particular task is called an assignment. Just like tasks, we want to know assignment start, finish, and duration, but we also want to know something else: the level of effort the resource is applying to complete a task. A resource may be capable of working 8 hours per day, but may be assigned to work only 4 hours a day (half its capacity) on a particular task. There are also task dependencies – a relation between two tasks that states that one task must end before another may start. A project is simply a collection of all of the above, and a project’s start and finish dates are inferred from the tasks that belong to it. Here are the classes:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace ProjectScheduling {
  /// <summary>A project.
  /// </summary>
  public class Project {
    /// <summary>The list of tasks in the project.
    /// </summary>
    public IList<Task> Tasks { get; private set; }
    
    /// <summary>The list of resources in the project.
    /// </summary>
    public IList<Resource> Resources { get; private set; }
    
    /// <summary>The list of task dependency links in the project.
    /// </summary>
    public IList<TaskDependency> Dependencies { get; private set; }

    public Project(IList<Task> tasks, IList<Resource> resources, IList<TaskDependency> links) {
      Tasks = tasks;
      Resources = resources;
      Dependencies = links;
    }

    public override string ToString() {
      StringBuilder build = new StringBuilder(40 + Tasks.Count * 20);
      build.AppendLine(new string('-', 40));
      build.AppendLine("PROJECT");
      build.AppendLine("TASKS");
      foreach (Task task in Tasks) {
        build.AppendLine(task.ToString());
      }
      build.AppendLine("LINKS");
      foreach (TaskDependency link in Dependencies) {
        build.AppendLine(link.ToString());
      }
      build.AppendLine("RESOURCES");
      foreach (Resource resource in Resources) {
        build.AppendLine(resource.ToString());
      }
      build.AppendLine(new string('-', 40));
      return build.ToString();
    }
  }

  /// <summary>A task.
  /// </summary>
  public class Task {
    private IEnumerable<Assignment> assignments;
    private static int nextID = 0;

    private Task(int id, string name, double duration, IEnumerable<Assignment> assignments) {
      ID = id;
      Name = name;
      Duration = duration;
      this.assignments = assignments;
    }

    /// <summary>A dummy invalid task.
    /// </summary>
    public static Task Invalid = new Task(-1, "** INVALID **", -1, null);

    /// <summary>A unique ID.
    /// </summary>
    public int ID { get; set; }

    /// <summary>The task name.
    /// </summary>
    public string Name { get; set; }

    /// <summary>The task duration (time unit unspecified).
    /// </summary>
    public double Duration { get; set; }

    /// <summary>The resource assignments for the task.
    /// </summary>
    public IEnumerable<Assignment> Assignments {
      get { return assignments; }
    }

    public Task(string name, double duration, IEnumerable<Assignment> assignments)
      : this(nextID++, name, duration, assignments) {
    }

    public override string ToString() {
      return String.Format("{0}: {1} duration = {2}", ID, Name, Duration);
    }
  }

  /// <summary>A finish-to-start dependency between tasks.
  /// </summary>
  public class TaskDependency {
    /// <summary>The predecessor task.
    /// </summary>
    public Task Source { get; set; }
    
    /// <summary>The successor task.
    /// </summary>
    public Task Destination { get; set; }

    public override string ToString() {
      return String.Format("{0} -> {1}", (Source ?? Task.Invalid).ID, (Destination ?? Task.Invalid).ID);
    }
  }

  /// <summary>An assignment, corresponding to a task and a resource.
  /// </summary>
  public class Assignment {
    /// <summary>The resource.
    /// </summary>
    public Resource Resource { get; set; }

    /// <summary>The rate at which work is performed.
    /// </summary>
    public double Units { get; set; }

    public Assignment(Resource resource, double units) {
      Resource = resource;
      Units = units;
    }

    public override string ToString() {
      return String.Format("r{0}: units = {1}", Resource.ID, Units);
    }
  }

  /// <summary>A resource.
  /// </summary>
  /// <remarks>
  /// A resource may correspond to a work resource (such as an employee),
  /// or a material resource (such as a machine).
  /// </remarks>
  public class Resource {
    private static int nextID = 0;

    /// <summary>A unique ID.
    /// </summary>
    public int ID { get; set; }

    /// <summary>The resource name.
    /// </summary>
    public string Name { get; set; }

    /// <summary>The maximum rate at which the resource can perform work.
    /// </summary>
    public double MaxUnits { get; set; }

    public Resource(string name, double maxUnits) {
      ID = nextID++;
      Name = name;
      MaxUnits = maxUnits;
    }

    public override string ToString() {
      return String.Format("{0}: {1} max units = {2}", ID, Name, MaxUnits);
    }
  }
}

 

It’s not too hard to populate these classes with data. In particular, a “fun” exercise is to read from the Microsoft Project XML schema (File –> Save As XML) to populate these data structures. A simpler exercise is to generate a random project:

    private static Project CreateProject(int taskCount) {
      System.Random random = new Random(0);
      int maxDuration = 5;
      int linkCount = Math.Max(taskCount / 10, 1);

      Resource[] resources = new Resource[] {
        new Resource("R1", 100.0),
        new Resource("R2", 100.0)
      };

      Task[] tasks = new Task[taskCount];
      for (int i = 0; i < tasks.Length; i++) {
        tasks[i] = new Task("t" + i, random.Next(1, maxDuration + 1), new Assignment[] { new Assignment(resources[i % resources.Length], 1.0) });
      }

      TaskDependency[] links = new TaskDependency[linkCount];
      for (int i = 0; i < links.Length; i++) {
        int source = random.Next(0, taskCount - 1);
        int dest = random.Next(source + 1, taskCount); // guaranteeing no cycles.
        links[i] = new TaskDependency { Source = tasks, Destination = tasks[dest] };
      }

      return new Project(tasks, resources, links);
    }

 

Next time we will write down the C# code for the model and hook it up to these data structures. Then we can see how the code works on real projects – the results will shock and amaze you. Or not.

Project scheduling and Solver Foundation revisited, Part I

Recently I was asked by a potential customer whether Solver Foundation could be used to solve project scheduling and resource allocation problems. The answer is yes! I reviewed my previous blog posts on the subject, but I found them to be a little too simplistic. In the next few posts I will try to build something a little more sophisticated.

Project scheduling problems usually involve establishing start and finish dates for activities. Often the goal is to find a schedule whose completion date is as soon as possible (although other goals such as total cost or “net present value” make sense too). There are also restrictions on the schedule. For example we may also have constraints between tasks: the start of a task cannot start before another finishes. If people (“resources”) are assigned to work on the activities then we may not be able to “double book” a task – that is, we cannot assign a resource to work on two activities simultaneously. Producing a schedule that honors resource availability is called “resource constrained project scheduling” (RCPS). Modeling the resource constraints is not easy to do, and it also makes the models themselves much more difficult to solve. RCPS is an NP-hard problem.

Julian built a nice MSF model for RCPS last year and blogged about it here. This is a perfectly good formulation for some situations. One of the concepts in the model is a “time slot”: a fixed window during which an activity (or “task”) can be scheduled. For each (task, resource, slot) tuple we can have a binary decision value that indicates whether the task is scheduled for a resource during the slot. Making sure that a resource is not double booked is not hard in this formulation: scan the decision values corresponding to a resource and make sure at most one is “true” for each time slot. For conference scheduling, where we know the time horizon and the duration of each task is the same, this is fine. But for other applications where tasks may have different lengths and we don’t actually know how long the project may take, this formulation is not as natural. Furthermore, notice that the size of the model depends on the number of time periods. So if you wanted to produce a schedule for a two year software development project with time periods of one day, you would very likely end up with a biiiiig model.

So I want to use a different formulation that handles time as a continuous variable, rather than breaking the schedule into slots. My approach is tried and true: steal. I did a brief survey of some recent research papers and picked one to implement as a Solver Foundation model. My source is: “Event-based MILP models for resource-constrained project scheduling problems” by Kone, Artigues, Lopez and Mongeau. You can download the paper here.

The formulation that seems most interesting (to me) is the one on page 9, equations 34 – 45. This formulation does not rely on time slots, it relies on events. An event is defined as an occasion when a task starts. Each event has a corresponding time represented as a continuous (real aka floating point) value. The start of the first event is the project start, which by convention we set to time t=0. In “time slot” based models the most interesting decision is “is this task active during time slot t”? In the event-based model we are about to describe, the two most interesting decisions are “is task t active just after the start of event e?” and “what is the start time of event e”? If we know these then we can find out anything else we want to know about the project. For example the finish of a task is determined by finding the time of the event where it starts and adding the duration. The project finish is the maximum task finish date.

The model contains the following constraints:

• Project finish. The project finish is the maximum finish date of any task in the project.

• Event zero. Event zero starts at time t = 0 by convention.

• Decision linking. The “active event” decisions z need to be linked to the “event start” decisions t.

• Event order. The start of event e+1 is never earlier than the start of event e.

• Contiguity. There are no gaps between events. This is a logical consequence of the definition of “event” given above.

• Sanity. Each task must be active at some point.

• Links. Precedence links must be obeyed. A precedence link between two tasks indicates that the first must end before the second can start.

• Resource. Resource availability must be honored.

It’s not stated explicitly, but notice that these constraints mean that tasks are scheduled without “splits”: once a task begins its execution is not interrupted. Looking at the constraints in the paper carefully, it seems there are three typos:

• Equation 37 says that f > e != 0. This is fine, but this does not account for resource overallocations during event 0 (when e = 0). So I think there should be another equation (37a): o t_f >= t_e + (z_i-e – (z_if – z_i(f-1)) – 1) * p_i
• In equation 39, the inequality should use <=, not =>.
• In equation 40, the inequality should use <=, not =>.

Now that we have a mathematical model for the problem we need to translate it into Solver Foundation Services calls. I’ll save that for the next post, following the same pattern as my office space allocation series.

Resource constrained scheduling; OML tutorials

Two weeks back I posted two articles showing how easy it is to model critical path scheduling using Microsoft Solver Foundation.  I received a few emails asking about various extensions; I will be covering those in upcoming posts.  Julian just wrote a great blog post that covers the most commonly requested extension – resource constrained scheduling.  If you are getting started with Solver Foundation and want to see an interesting, instructive example, I encourage you to check out his post.  Two things that I really like about his OML:

1. He separates the data from the model description using Parameters.
2. He relies on the Foreach construct to define his constraints.  It results in a very clean model definition.

Julian mentions it in his post, but I also want to call out another great resource for learning OML.  Erwin Kalvalagen has written an OML tutorial which includes several interesting examples.  It’s a great complement to the Excel Programming Primer that is part of the Solver Foundation documentation.