Какой хороший подход / шаблон для решения этой проблемы планирования

Question

У меня есть объект

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

    public DateTime? StartDate { get; set; }
}

, который имеет зависимости от других экземпляров. Например:

(читать «<-» как «зависит от») </p>

• B <- A </li>
• C <- A </li>
• D <- B, C </li>

и

• Q <- P </li>
• R <- Q </li>

Учитывая список заданий * и EndDate, мне нужно установить StartDate для каждой задачи так, чтобы все они были завершены EndDate. Задачи могут выполняться параллельно, где это возможно, поэтому ....

A должен быть заполнен до B и C (что может быть сделано одновременно), а D может быть запущен только после завершения B и C.

R должен запускаться после Q, после P, но они могут выполняться в пареллах к A B C и D.

* список будет завершен, все зависимости будут присутствовать в списке

Спасибо за любой совет Andrew

Answer 1

Вам необходимо вычислить критический путь. См. этот вопрос , если это поможет.

В противном случае это простая задача динамического программирования.

Answer 2

A DAG и Топологическая сортировка ?

Answer 3

Спасибо за советы каждого, топологическая сортировка была полезна, но я думаю, что решил ее проще ...

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);
        }
    }
}

Answer 4

    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;
        }

где-то в основном:

            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 5

Для небольших графиков просто вычислите дату начала рекурсивно - дата начала D будет min(B.StartDate,C.StartDate) - D.Length.

Для больших графиков выполните топологическую сортировку, после чего вы можете выполнять вычисления итеративно.

Answer 6

Звучит скорее как синхронизация. То есть в потоке вы бы использовали WaitHandles.

A запускается и передает B дескриптор ожидания И C дескриптор ожидания

Как только А заканчивает запуск B и C, из-за того, что сигнализирует о ожидании

D имеет ручку ожидания, которая ожидает ЛЮБОГО на B и C, поэтому тот, кто когда-либо финиширует первым, подаст D