Permutations with Multiple Lists

I need to place workers into jobs for a given shift. Workers set a preference order as to which job they wish to work. The Workers with the lowest number of hours get the first preference at a job. Only one worker can work a particular job.

I have tried to solve this by creating a jagged array. The array is sorted by workers with the lowest hours. Each sub array is a particular workers preference list. The numbers in the array is the job code. Then I generated permutations until I get a valid solution.

For Example, below is开发者_如何学Go a list of 28 workers along with each workers job preference.

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] contains the first workers preference list. prererence[1] contains the second workers perference list, and so on. In this example the first worker has selected to work jobs 1,2,3,4,5,6,7,8,11,12,13,14,15. The correct solution would be: 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.

The issue I have is performance. I tried iterating using both recursive and non- recursive loops and the performance is terrible. My thought is there must be a different approach to solving the problem or a library that already does this which I could purchase. Thanks in advance for any help.

---

When you have

1. your workers sorted according to "who gets to pick first"
2. the preferences are sorted in descending preference and
3. each worker is supposed to be handed only one assignment

then i think the job allocation algorithm should be possible to execute in something like O(n2 log(n))) using two cursors and a list of already allocated jobs..

Are there additional solution optimization requirements that you are not stating?: E.g.

1. You need to find the solution where the fewest possible workers are allocated jobs for which they have no preference at all. or
2. The sum of the preference rank for all the allocated jobs should be the lowest mathematically possible.

If so the algorithm will be more complex.

If by valid solution you mean any allocation of jobs where all workers have gotten a job from their preference list, then I would question the applicability of your algorithm as an answer to the real world shift work assignment problem. You will frequently end up without a solution.

---

Assuming strict adherence to Seniority/Priority (I know the hourly job postings at my company are strict w.r.t. to seniority) you could simplify things:

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
}

Now if you don't have a strict adherence policy, then you're looking at an optimization problem and the question becomes do you allow the potential for a higher priority individual getting a lower preference job code?

Most optimization algorithms don't have the same concept of "fair" your shift workers may have.

---

If you remove an employee from the list as they're assigned to a job, subsequent job selections will go faster. Another way to look at it is to walk down the list of employees once, and for each employee, walk down their job preferences and assign them to the first open job in their preference list. This way you only look at each employee once.