Whats a good approach/pattern to solve this scheduling problem

Question

I have an object

public class Task
{
    public TimeSpan Length { get; set; }
    public IList<Task> Dependencies { get; set; }

    public DateTime? StartDate { get; set; }
}

which has dependencies on other instances. For example:

(read "<-" as "depends on")

• B <- A
• C <- A
• D <- B,C

and

• Q <- P
• R <- Q

Given a list of Tasks* and an EndDate, I need to set the StartDate on each task such that they will all be completed by the EndDate. Tasks may run in parallel where possible, so....

A has to be completed before B and C (which can be done at the same time), and D can only be run after B and C are both complete.

R must run after Q, after P, but these can be run in parelell to A B C and D.

* the list will be complete, all dependencies will be present in the list

Thanks for any advice Andrew

Answer 1

A DAG and Topological Sort?

Answer 2

It sounds more of a syncronization activity. I.e. in threading you would use WaitHandles.

A starts and passes B a wait handle AND C a wait handle

Once A finishes B and C start due to the wait handle being signalled

D has a wait handle that waits for ANY on B and C , so who ever finishs first will signal D

Answer 3

For small graphs, just calculate the start date recursively - the start date of D will be min(B.StartDate,C.StartDate) - D.Length.

For large graphs, perform a topological sort then you can perform the calculations iteratively.

Answer 4

You need to compute the critical path. See this question if it helps.

Otherwise, it's an easy dynamic programming problem.

Answer 5

    public class Task
    {
        public long Length;
        public List<Task> Dependencies = new List<Task>();
        public DateTime StartDate;
        public DateTime EndDate;

        public void CompleteBaseSchedule()
        {
            DateTime startDate = DateTime.MinValue;
            foreach (Task task in Dependencies)
            {
             startDate = (startDate < task.EndDate) ? task.EndDate : startDate;
                task.CompleteBaseSchedule();

            }
            this.StartDate = startDate;
            this.Length = this.EndDate.Ticks - this.StartDate.Ticks;
        }

somewhere in the main:

            Task task1 = new Task();
            task1.EndDate = new DateTime(2009, 3, 3);
            Task task2 = new Task();
            task1.EndDate = new DateTime(2009, 3, 5);
            Task task3 = new Task();
            task1.EndDate = new DateTime(2009, 3, 2);
            Task task4 = new Task();
            task1.EndDate = new DateTime(2009, 3, 6);
            task4.Dependencies.AddRange(new Task[]{ task1, task2, task3 });

            task4.CompleteBaseSchedule();
            Console.WriteLine(task4.StartDate);
            Console.ReadLine();

Answer 6

Thanks for everyones' advice, the Topological sort stuff was useful, but I think i've solved it an easier way...

public class Scheduler
{
    private readonly IEnumerable<Task> tasks;
    private readonly DateTime endDate;

    public Scheduler(IEnumerable<Task> tasks, DateTime endDate)
    {
     this.tasks = tasks;
     this.endDate = endDate;
    }

    public void Schedule()
    {
     var terminators = FindTerminators();
     SetStartDatesRecursively(terminators, endDate);
    }

    public ICollection<Task> FindTerminators()
    {
     IList<Task> terminators = new List<Task>();

     foreach(var task in tasks)
     {
      var dependencies = this.tasks.Where(x => x.Dependencies.Contains(task));
      if (dependencies.Count() == 0)
       terminators.Add(task);
     }

     return terminators;
    }

    public void SetStartDatesRecursively(IEnumerable<Task> tasks, DateTime endDate)
    {
     foreach(var task in tasks)
     {
      var startDate = endDate - task.Length;

      if (task.StartDate.HasValue)
       task.StartDate = startDate < task.StartDate ? startDate : task.StartDate;
      else
       task.StartDate = startDate;

      SetStartDatesRecursively(task.Dependencies, task.StartDate.Value);
     }
    }
}