Планирование задач C# с помощью MS Solver Framework

Я хочу запланировать задачи с помощью Microsoft Solver Framework. На данный момент у меня есть простая цель — просто упорядочить задачи в очереди, чтобы получить минимальное время проекта. (позже я хочу иметь более одной очереди). Я попытался подойти к этому со следующей настройкой:

  • Decision:
    • projectFinish
    • Начало
    • финиш
  • Parameter:
    • duration
  • Constraint:
    • start + duration = finish
    • не более одной задачи одновременно
    • projectFinish после завершения всех задач
  • Goal:
    • minimize projectFinish

Вот мой код до сих пор

    static void Main(string[] args) {
        var data = new List<Task>() {
            new Task(){ Duration = 1, Name = "task0"},
            new Task(){ Duration = 1, Name = "task1"},
            new Task(){ Duration = 1, Name = "task2"},
        };

        SolveScheduling(data);
    }

    public class Task {
        private static int id_counter = 0;
        public Task() { ID = id_counter++; }
        public int ID { get; private set; }
        public string Name { get; set; }
        public double Duration { get; set; }
    }

    private static void SolveScheduling(IEnumerable<Task> data) {

        SolverContext context = SolverContext.GetContext();
        Model model = context.CreateModel();

        var set = new Set(Domain.Any,"TaskSet");


        var projectFinish = new Decision(Domain.IntegerNonnegative, "projectFinish");
        model.AddDecision(projectFinish);

        var taskSet = new Set(Domain.Any, "tasks");

        var durations = new Parameter(Domain.RealNonnegative, "durations", taskSet);
        durations.SetBinding(data, "Duration", "Name");
        var ids = new Parameter(Domain.Integer, "ids", taskSet);
        ids.SetBinding(data, "ID", "Name");
        var starts = new Decision(Domain.RealNonnegative, "starts", taskSet);
        var finishs = new Decision(Domain.RealNonnegative, "finishs", taskSet);

        model.AddDecisions(starts, finishs);
        model.AddParameters(durations, ids);

        // Constraints

        // start + duration = finish
        model.AddConstraint("constraint0", Model.ForEach(taskSet, (t) => starts[t] + durations[t] == finishs[t]));
        // Tasks after each other
        model.AddConstraint("constraint1", Model.ForEach(taskSet, t =>
            Model.ForEachWhere(taskSet, t2 =>  Model.Or(finishs[t] < starts[t2] , starts[t] > finishs[t2]), (t2) => ids[t] != ids[t2])));
        // projectFinish after all tasks finished
        model.AddConstraint("constraint2", Model.ForEach(taskSet, t => projectFinish >= finishs[t]));

        // Goals
        model.AddGoal("goal0", GoalKind.Minimize, projectFinish); 


        Solution solution = context.Solve();//new SimplexDirective());

        Report report = solution.GetReport();
        Console.WriteLine(@"===== report =====");
        Console.Write("{0}", report);
        Console.ReadLine();
    }

Теперь проблема в том, что для решения этого требуется вечность (хотя это всего 3 задачи и 1 очередь). Что мне здесь не хватает и как я могу улучшить скорость решения.

Обновить

Я нашел решение для моей проблемы. Если у вас есть какие-либо улучшения, не стесняйтесь комментировать. Вот мой код:

        SolverContext context = SolverContext.GetContext();
        Model model = context.CreateModel();

        // === Sets ===
        var taskSet = new Set(0,data.Count(), 1);

        // === Parameters ===
        var duration = new Parameter(Domain.RealNonnegative, "durations", taskSet);
        var id = new Parameter(Domain.RealNonnegative, "id", taskSet);
        duration.SetBinding(data, "Duration", "ID");
        id.SetBinding(data, "ID", "ID");

        model.AddParameters(duration, id);

        // === Decisions ===
        var projectFinish = new Decision(Domain.RealNonnegative, "projectFinish");
        var start = new Decision(Domain.RealNonnegative, "starts", taskSet);
        var finish = new Decision(Domain.RealNonnegative, "finishs", taskSet);

        model.AddDecisions(projectFinish, start, finish);

        // === Constraints ===
        model.AddConstraint("constraint0", start[0] == 0);
        // start + duration = finish
        model.AddConstraint("constraint1", Model.ForEach(taskSet, (t) => start[t] + duration[t] == finish[t]));           
        // projectFinish after all tasks finished
        model.AddConstraint("constraint2", Model.ForEach(taskSet, t => projectFinish >= finish[t]));
        // not more than one task at a time
        model.AddConstraint("constraint3", Model.ForEach(taskSet, t =>
            Model.ForEachWhere(taskSet, t2 => Model.Or(finish[t] < start[t2], start[t] > finish[t2]), (t2) => id[t] != id[t2])));


        // === Goals ===
        model.AddGoal("goal0", GoalKind.Minimize, projectFinish); // minimieren der projekt zeit

        // === Solve ===
        context.CheckModel();
        Solution solution = context.Solve();

person Yellown    schedule 14.10.2016    source источник


Ответы (1)


Я нашел решение, которое работает для меня. Я изменил набор задач

var taskSet = new Set(0, data.Count(), 1);

и добавил новое ограничение

model.AddConstraint("constraint", starts[0] == 0);

я обновил вопрос

person Yellown    schedule 17.10.2016