Перестановки с несколькими списками

Question

Мне нужно устроить рабочих на работу для данной смены. Рабочие устанавливают порядок предпочтений относительно того, на какую работу они хотят работать. Работники с наименьшим количеством часов получают первое предпочтение на работе. Только один работник может выполнять определенную работу.

Я попытался решить эту проблему, создав зубчатый массив. Массив отсортирован по рабочим с наименьшим количеством часов. Каждый вложенный массив представляет собой определенный список предпочтений работников. Числа в массиве - это код задания. Затем я генерировал перестановки, пока не получил правильное решение.

Например, ниже приведен список из 28 работников вместе с предпочтениями работы каждого работника.

int[][] preference = {
    new int[] {1,2,3,4,5,6,7,8,11,12,13,14,15},
    new int[] {2,4,5,6,7,8,11,12,13,14,15},
    new int[] {1,3,6,7,8,9,10,14,15,18,19,22,23,24,26,27,29,30,32,34,35,25,36},
    new int[] {4,5,12,13},
    new int[] {9,10,11,14,15,1,2,6},
    new int[] {9,10,11,14,2,6,18,19,27,29,30,31,32,35},
    new int[] {11,12,13,14,2,4,5,6},
    new int[] {12,13,4,5},
    new int[] {9,10,11,13,14,15,1,2,6,7,8,18,19,21,22,23,24,26,27,28,29,30,31,32,34,35,16,17,33,36},
    new int[] {1,2,9,10,11,14,15,18,19,30,31,32,35,37,33},
    new int[] {4,13,18,19,35},
    new int[] {18,19,35},
    new int[] {21,22,23,24,18,19},
    new int[] {22,23,24,25,18,19,16,17},
    new int[] {18,19,23,24,35},
    new int[] {18,19,23,24,35},
    new int[] {27,26,28,29,30,32,34,35,36},
    new int[] {27,26,30,32,34,35,36},
    new int[] {28,29,30,31,32,33,35},
    new int[] {28,29,30,31,32,33,26,35,36},
    new int[] {26,29,30,31,32,34,35,36},
    new int[] {28,29,31,32,33,26,35,36},
    new int[] {27,28,29,30,31,32,35,33,1,2,3,9,10,11,14,18,19,6,15},
    new int[] {34,35,36,26,27,31,32},
    new int[] {31,32,34,35,2,11,14,18,19,23,24,6,15,16,17,20},
    new int[] {37,29,30,31,32,35,33,36,2,9,10,11,14,18,19,23,24,6,15,16,17},
    new int[] {18,19,35},
    new int[] {18,19,35},
};

preference[0] содержит первый список предпочтений работников. prererence[1] содержит второй список предпочтений рабочих и т. Д. В этом примере первый работник выбрал для работы 1,2,3,4,5,6,7,8,11,12,13,14,15. Правильное решение будет: 1,2,3,4,9,10,11,12,14,15,13,18,21,22,23,24,27,26,28,29,30,31,32,34,6,37,19,35.

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

Answer 1

Если у вас есть

1. , ваши работники отсортированы в соответствии с «кто выбирает первым»
2. , предпочтения сортируются по убыванию, и
3. каждый работникпредполагается, что будет передано только одно назначение

, тогда я думаю, что алгоритм распределения заданий должен быть в состоянии выполнить что-то вроде O (n2 log (n))), используя два курсора и список уже распределенных заданий..

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

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

Если так, то алгоритм будет более сложным.

Если под верным решением вы подразумеваете любое распределение рабочих мест, когда все работники получили работу по своему предпочтению.В таком случае я бы поставил под сомнение применимость вашего алгоритма в качестве ответа на реальную проблему назначения сменной работы.Вы часто будете в конечном итоге без решения.

Answer 2

Предполагая строгое соблюдение старшинства / приоритета (я знаю, что почасовые объявления о вакансиях в моей компании строго относятся к старшинству), вы можете упростить вещи:

var availableJobs = new List<int>(... jobs here ...);
var usedJobs = HashSet<int>();
var selectedJobs = new Dictionary<int,int>(); // keyed by employee #

for (int ww = 0; ww < preference.Count(); ++ww)
{
    // this will throw an exception if strict ordering is unsolvable
    try
    {
        // Remove the try...catch if job cannot be 0 and use FirstOrDefault
        int job = preference[ww].First(jj => !usedJobs.Contains(jj));
        selectedJobs.Add(ww, job);
        usedJobs.Add(job);
    }
    catch(InvalidOperationException ioe)
    {
        Console.WriteLine("Cannot allocate job code to worker: {0}", ww);
        Console.WriteLine("No job preference matches.");
        Console.WriteLine("    Job codes avaliable");
        Console.WriteLine("    -------------------");
        foreach (var jobCode in availableJobs.Except(usedJobs))
        {
             Console.WriteLine("{0}", jobCode);
        }

        break;
    }
}

if (selectedJobs.Count() == preference.Count())
{
    // jobs have been assigned per worker
}

Теперь, если у вас нет строгой приверженностиполитика, а затем вы смотрите на проблему оптимизации, и возникает вопрос: допускаете ли вы возможность для лица с более высоким приоритетом получать код задания с более низким предпочтением?

Большинство алгоритмов оптимизации не имеют той же концепции "честно "могут иметь ваши сменные работники.

Answer 3

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