Миницинк: проблема с магазином, свести к минимуму слишком долго - PullRequest
Новая
       6

Миницинк: проблема с магазином, свести к минимуму слишком долго

0 голосов
/ 21 декабря 2018

У меня есть версия задачи магазина, где задачи могут иметь множественную зависимость (жесткое ограничение) и иметь крайний срок (мягкое ограничение).

Поиск решения, при котором зависимость встречается, а ее нетПерекрытие не проблема, проблема заключается в том, когда я пытаюсь «минимизировать» количество задач, которые нарушают сроки.Когда я использую «минимизировать» в «решить», процесс запуска занимает более 30 минут и не завершается (если я использую «удовлетворить», он заканчивается через 20 секунд) (для 3000 задач с использованием решателя Chuffed).

Любые идеи о том, как применить мягкое ограничение (крайний срок) в разумные сроки?

.mzn файл: 

include "disjunctive.mzn";

int: dispositiveQty;
int: taskQty;

set of int: DEVICE = 0..dispositiveQty;
set of int: TASK = 1..taskQty;

array[TASK] of int: duration;
array[TASK] of DEVICE: devTask; % device on which the task will run
array[TASK] of set of TASK: dependency; % which tasks has to be finished before the task can start
array[TASK] of int: maxDateTask; % deadline of the task

int: maxTime = sum(t in TASK)(duration[t]);

array[TASK] of var 0..maxTime: taskStart;

constraint forall(t in TASK where dependency[t] != {})
  (taskStart[t] >= max(d in dependency[t])(taskStart[d] + duration[d])); 

int: dev1 = 125;
int: dev2 = 5;
int: dev3 = 18;
int: dev5 = 2;
int: dev6 = 786;
int: dev7 = 291;
int: dev8 = 3;
int: dev9 = 226;
int: dev10 = 906;
int: dev11 = 720;
int: dev12 = 4;
int: dev13 = 36;
int: dev15 = 4;
int: dev16 = 2;
int: dev17 = 14;
int: dev18 = 42;
int: dev21 = 2;

constraint let{array[1..dev1] of var 0..maxTime: dev1Start = [taskStart[i] | i in TASK where devTask[i] == 1],
array[1..dev1] of var int: dev1Duration = [duration[i] | i in TASK where devTask[i] == 1]
} in disjunctive(dev1Start, dev1Duration);

constraint let{array[1..dev2] of var 0..maxTime: dev2Start = [taskStart[i] | i in TASK where devTask[i] == 2],
array[1..dev2] of var int: dev2Duration = [duration[i] | i in TASK where devTask[i] == 2]
} in disjunctive(dev2Start, dev2Duration);

constraint let{array[1..dev3] of var 0..maxTime: dev3Start = [taskStart[i] | i in TASK where devTask[i] == 3],
array[1..dev3] of var int: dev3Duration = [duration[i] | i in TASK where devTask[i] == 3]
} in disjunctive(dev3Start, dev3Duration);

constraint let{array[1..dev5] of var 0..maxTime: dev5Start = [taskStart[i] | i in TASK where devTask[i] == 5],
array[1..dev5] of var int: dev5Duration = [duration[i] | i in TASK where devTask[i] == 5]
} in disjunctive(dev5Start, dev5Duration);

constraint let{array[1..dev6] of var 0..maxTime: dev6Start = [taskStart[i] | i in TASK where devTask[i] == 6],
array[1..dev6] of var int: dev6Duration = [duration[i] | i in TASK where devTask[i] == 6]
} in disjunctive(dev6Start, dev6Duration);

constraint let{array[1..dev7] of var 0..maxTime: dev7Start = [taskStart[i] | i in TASK where devTask[i] == 7],
array[1..dev7] of var int: dev7Duration = [duration[i] | i in TASK where devTask[i] == 7]
} in disjunctive(dev7Start, dev7Duration);

constraint let{array[1..dev8] of var 0..maxTime: dev8Start = [taskStart[i] | i in TASK where devTask[i] == 8],
array[1..dev8] of var int: dev8Duration = [duration[i] | i in TASK where devTask[i] == 8]
} in disjunctive(dev8Start, dev8Duration);

constraint let{array[1..dev9] of var 0..maxTime: dev9Start = [taskStart[i] | i in TASK where devTask[i] == 9],
array[1..dev9] of var int: dev9Duration = [duration[i] | i in TASK where devTask[i] == 9]
} in disjunctive(dev9Start, dev9Duration);

constraint let{array[1..dev10] of var 0..maxTime: dev10Start = [taskStart[i] | i in TASK where devTask[i] == 10],
array[1..dev10] of var int: dev10Duration = [duration[i] | i in TASK where devTask[i] == 10]
} in disjunctive(dev10Start, dev10Duration);

constraint let{array[1..dev11] of var 0..maxTime: dev11Start = [taskStart[i] | i in TASK where devTask[i] == 11],
array[1..dev11] of var int: dev11Duration = [duration[i] | i in TASK where devTask[i] == 11]
} in disjunctive(dev11Start, dev11Duration);

constraint let{array[1..dev12] of var 0..maxTime: dev12Start = [taskStart[i] | i in TASK where devTask[i] == 12],
array[1..dev12] of var int: dev12Duration = [duration[i] | i in TASK where devTask[i] == 12]
} in disjunctive(dev12Start, dev12Duration);

constraint let{array[1..dev13] of var 0..maxTime: dev13Start = [taskStart[i] | i in TASK where devTask[i] == 13],
array[1..dev13] of var int: dev13Duration = [duration[i] | i in TASK where devTask[i] == 13]
} in disjunctive(dev13Start, dev13Duration);

constraint let{array[1..dev15] of var 0..maxTime: dev15Start = [taskStart[i] | i in TASK where devTask[i] == 15],
array[1..dev15] of var int: dev15Duration = [duration[i] | i in TASK where devTask[i] == 15]
} in disjunctive(dev15Start, dev15Duration);

constraint let{array[1..dev16] of var 0..maxTime: dev16Start = [taskStart[i] | i in TASK where devTask[i] == 16],
array[1..dev16] of var int: dev16Duration = [duration[i] | i in TASK where devTask[i] == 16]
} in disjunctive(dev16Start, dev16Duration);

constraint let{array[1..dev17] of var 0..maxTime: dev17Start = [taskStart[i] | i in TASK where devTask[i] == 17],
array[1..dev17] of var int: dev17Duration = [duration[i] | i in TASK where devTask[i] == 17]
} in disjunctive(dev17Start, dev17Duration);

constraint let{array[1..dev18] of var 0..maxTime: dev18Start = [taskStart[i] | i in TASK where devTask[i] == 18],
array[1..dev18] of var int: dev18Duration = [duration[i] | i in TASK where devTask[i] == 18]
} in disjunctive(dev18Start, dev18Duration);

constraint let{array[1..dev21] of var 0..maxTime: dev21Start = [taskStart[i] | i in TASK where devTask[i] == 21],
array[1..dev21] of var int: dev21Duration = [duration[i] | i in TASK where devTask[i] == 21]
} in disjunctive(dev21Start, dev21Duration);

var int: aboveDeadline = sum(i in TASK where maxDateTask[i] < (taskStart[i] + duration[i]))(1);

solve :: int_search([taskStart[t] | t in TASK], input_order, indomain_min, complete) satisfy;%minimize aboveDeadline;

.dzn файл: https://www.dropbox.com/s/94n7fqxzcai5tvf/testData.dzn?dl=0

(я не могу поместить файл .dzn напрямую, потому что он превышает ограничение по количеству символов)

1 Ответ

0 голосов
/ 28 декабря 2018

Вводя новый параметр tasks, который содержит количество задач на устройство, все ограничения disjunctive могут быть сгенерированы одним циклом forall.(Еще лучше было бы переместить параметр tasks в файл данных, тогда одна и та же модель могла бы использоваться для разных экземпляров).

Редактировать : tasks также может быть напрямую получено как array[DEVICE] of int: tasks = [sum(t in TASK)(d == devTask[t]) | d in DEVICE];, учитывая, что DEVICE переопределено как set of int: DEVICE = 1..dispositiveQty;

Используя модель ниже, Chuffedнаходит решение для большего экземпляра в ~ 10 с.

include "disjunctive.mzn";

int: dispositiveQty;
int: taskQty;

set of int: DEVICE = 0..dispositiveQty;
set of int: TASK = 1..taskQty;

array[TASK] of int: duration;
array[TASK] of DEVICE: devTask; % device on which the task will run
array[TASK] of set of TASK: dependency; % which tasks has to be finished before the task can start
array[TASK] of int: maxDateTask; % deadline of the task

int: maxTime = sum(t in TASK)(duration[t]);

array[TASK] of var 0..maxTime: taskStart;

constraint forall(t in TASK, d in dependency[t])
  (taskStart[t] >= taskStart[d] + duration[d]); 

array[int] of int: tasks = [125, 5, 18, 0, 2, 786, 291, 3, 226, 906, 720, 4, 36, 0, 4, 2, 14, 42, 0, 0, 2];

constraint forall(d in index_set(tasks) where tasks[d] > 0)
    (let {array[1..tasks[d]] of var int: taskStarts = [taskStart[i] | i in TASK where devTask[i] == d]; 
           array[1..tasks[d]] of var int: durations = [duration[i] | i in TASK where devTask[i] == d]} 
      in disjunctive(taskStarts, durations));

var int: aboveDeadline = sum(i in TASK)(bool2int(taskStart[i] + duration[i] > maxDateTask[i]));

solve :: int_search(taskStart, input_order, indomain_min, complete)
minimize aboveDeadline;

output ["aboveDeadline=\(aboveDeadline)"];
...