Проблема, которую я хочу решить, состоит из примерно 800 задач, которые должны быть назначены примерно 120 работникам. Рабочие должны иметь квалификацию для выполнения задачи и иметь только определенное количество часов в неделю. Около 80 % заданий уже предварительно назначены. Это означает, что их следует сохранить, но если остальные 20% не могут быть решены, предварительные задания могут быть нарушены.
У меня уже есть модель, использующая решатель Choco, который использует штрафы, если предварительное назначение нарушается, и цель состоит в том, чтобы минимизировать штраф. Однако я думаю, что это не очень эффективно, потому что решатель не начнет стратегию поиска с присвоением предварительно назначенных переменных. Я уже задавал вопрос специально для Choco здесь (Как определить начальную точку распространения в Choco 3.3).
Но есть ли другой решатель, где это можно сделать проще? Может быть, лучше написать свой собственный решатель? Буду признателен за любые предложения.
РЕДАКТИРОВАТЬ: я пытался написать свою собственную стратегию Choco. Для небольшой проблемы работает нормально, а для большой не находит решения. Я не уверен, разрешено ли все, что я делаю в getDecision (например, проверка isInstantiated), и я не могу найти документацию или руководство о том, как написать стратегию, расширяющую AbstractStrategy. Буду признателен за любые подсказки, в чем может быть проблема. (Чем выше абсолютный приоритет в матрице prios, тем раньше должна быть назначена переменная. Если приоритет отрицательный, следует присвоить 0, если положительный — 1. Наивысший приоритет — 9999)
public class PriorityStrategy extends AbstractStrategy<IntVar> {
int[] prios;
// Search strategy parameters
VariableSelector<IntVar> variableSelector;
IntValueSelector valueSelectorLB;
IntValueSelector valueSelectorUB;
DecisionOperator<IntVar> decisionOperator;
// object recycling management
PoolManager<IntDecision> decisionPool;
int currentIndex = -1;
HashMap<IntVar, Integer> bestsMap = new HashMap<IntVar, Integer>();
public PriorityStrategy(IntVar[] vars, int[] prios) {
super(vars);
this.prios = prios;
valueSelectorLB = new IntDomainMin();
valueSelectorUB = new IntDomainMax();
variableSelector = new Random<IntVar>(123); //new Occurrence<IntVar>();
this.decisionPool = new PoolManager<>();
}
@Override
public Decision<IntVar> getDecision() {
IntVar next = null;
List<IntVar> bests = new ArrayList<IntVar>();
int bestPrio = 0;
for (int i = 0; i < vars.length; i++) {
int currentPrio = Math.abs(prios[i]);
if (currentPrio >= bestPrio && !vars[i].isInstantiated() ||
(next == null && !vars[i].isInstantiated())) {
if(currentPrio == 9999) {
currentIndex = i;
bests.clear();
bestsMap.clear();
return computeDecision(vars[i]);
}
if(currentPrio > bestPrio) {
bestPrio = currentPrio;
bests.clear();
bestsMap.clear();
}
bests.add(vars[i]);
bestsMap.put(vars[i], i);
}
}
if(bests.size()>0) {
next = variableSelector.getVariable(bests.toArray(new IntVar[bests.size()]));
currentIndex = bestsMap.get(next);
}
return computeDecision(next);
}
@Override
public Decision<IntVar> computeDecision(IntVar variable) {
if (variable == null || variable.isInstantiated()) {
return null;
}
int currentVal;
if(prios[currentIndex] > 0){
currentVal = valueSelectorUB.selectValue(variable);
} else {
currentVal = valueSelectorLB.selectValue(variable);
}
System.out.println("Idx " + currentIndex);
IntDecision current = decisionPool.getE();
if (current == null) {
current = new IntDecision(decisionPool);
}
current.set(variable, currentVal, DecisionOperator.int_eq);
return current;
}
}