Решение задания со многими заданиями

Задача, которую я хочу решить, состоит из около 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;
        }

    }

1 ответ

Почему бы вам не изменить стратегию поиска решателя так, чтобы он начинался с предварительно назначенных переменных? Это описано в документации.

Другие вопросы по тегам