Задача смены сотрудников - связать миссии вместе - PullRequest
Новая
       20

Задача смены сотрудников - связать миссии вместе

4 голосов
/ 14 апреля 2019

У меня есть список Employee и список Mission. У каждой миссии есть время начала и продолжительность.

В модели cp (Google CpSat, из пакета or-tools) я определил shifts = Dictionary<(int,int),IntVar>, где shifts[(missionId, employeeId)] == 1, если и только если эта миссия выполняется этим сотрудником.

Мне нужно назначить каждую миссию ровно одному сотруднику, и, очевидно, один сотрудник не может выполнять две миссии одновременно. Я уже написал эти два жестких ограничения, и они работают нормально.

Проблема:

Теперь некоторые миссии «связаны» вместе и должны выполняться одним и тем же сотрудником. Они хранятся следующим образом:

linkedMissions = {{1,2}, {3,4,5}}

Здесь миссии 1 и 2 должны выполняться совместно одним и тем же сотрудником, и то же самое для миссий 3, 4 и 5.

Чтобы написать это последнее ограничение, я собрал для каждого сотрудника список всех смен, которые должны быть связаны друг с другом, а затем сделал их равными. 

foreach (var employee in listEmployeesIds)
foreach (var missionGroup in linkedMissionsIds)
{
    var linkedShifts = shifts
        .Where(o => o.Key.Item2 == employee
                    && missionGroup.Contains(o.Key.Item1))
        .Select(o => o.Value)
        .ToList();

    for (var i = 0; i < linkedShifts.Count - 1; i++) 
        model.Add(linkedShifts[i] == linkedShifts[i + 1]);
}

Однако решатель говорит мне, что модель недостижима, но с бумагой и ручкой я легко могу найти рабочее планирование. У меня 35 сотрудников и 25 миссий, миссии, которые связаны друг с другом, не пересекаются, поэтому проблем быть не должно.

EDIT:

В качестве альтернативного подхода, предложенного @Laurent Perron, я пытался использовать одни и те же логические переменные для всех смен, которые должны быть вместе: 

var constraintBools = new List<IntVar>();

foreach (var missionGroup in linkedMissionsIds) {
    var constraintBools = new List<IntVar>();
    foreach (var employee in listEmployeesIds)
    {
        var linkedShifts = shifts
          .Where(o => o.Key.Item2 == employee
                    && missionGroup.Contains(o.Key.Item1))
          .Select(o => o.Value)
          .ToList();

        var constraint = model.NewBoolVar($"{linkedShifts.GetHashCode()}");
        model.AddBoolAnd(linkedShifts).OnlyEnforceIf(constraint);
        constraintBools.Add(constraint);
    }
    model.AddBoolOr(constraintBools);
}

Но теперь ограничение просто не работает: связанные изменения не осуществляются одним и тем же сотрудником.

Что не так в моих рассуждениях? Почему моя модель неосуществима?

...