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.

Author: natebrix

Follow me on twitter at @natebrix.

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