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.