#c# #.net #linear-programming #solver #ms-solver-foundation
#c# #.net #линейное программирование #решатель #ms-solver-foundation
Вопрос:
Я хочу планировать задачи с помощью Microsoft Solver Framework. На данный момент у меня есть простая цель — просто упорядочить задачи в очереди, чтобы получить минимальное время на проект. (позже я хочу иметь более одной очереди). Я попытался подойти к этому со следующей настройкой:
- Решение:
- Завершение проекта
- начать
- готово
- Параметр:
- Продолжительность
- Ограничение:
- начало продолжительность = завершение
- не более одной задачи одновременно
- Завершение проекта после завершения всех задач
- Цель:
- свернуть проект до конца
Вот мой код на данный момент
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();
Ответ №1:
Я нашел решение, которое работает для меня. Я изменил набор задач
var taskSet = new Set(0, data.Count(), 1);
и добавлено новое ограничение
model.AddConstraint("constraint", starts[0] == 0);
Я обновил вопрос