6
$\begingroup$

I have to manage shifts of a variable number of people inside several rooms for a week.
Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same for everyone.
Every person could ask for specific shifts and this could be accepted if a suitable solution can be found.
I could have other constraints, but let's face this very basic situation.

Now the questions:

  1. Which algorithm should I study and use?
  2. Is there some free library I can use for this purpose?
  3. Is there something I can use for C#?
$\endgroup$
  • $\begingroup$ We can help you with the first question, but the two other are off-topic here. $\endgroup$ – Yuval Filmus Mar 21 at 22:22
  • $\begingroup$ Thanks @YuvalFilmus, it will be enough, really!! I have no idea how to approach the problem. I started watching ORTools by Google and I'm thinking about using Assignment part (developers.google.com/optimization/assignment/simple_assignment) but I'm not sure I can. Anyway if people can help me to find the best (or a good) algorithm then I can find the lirary or write all the code by myself. $\endgroup$ – Marco Mar 21 at 22:25
  • 1
    $\begingroup$ There is probably a standard solution out there. In practice, a greedy approach would probably work. A more sophisticated approach is to model the situation as a bipartite graph, and repeatedly find maximum matchings. $\endgroup$ – Yuval Filmus Mar 21 at 22:27
  • 2
    $\begingroup$ If you can discretize time in 1h slots, Hungarian algorithm would do it. $\endgroup$ – Vince Mar 22 at 10:32
  • 1
    $\begingroup$ @ Exactly, for N workers and M tasks, you generate M/N working hour nodes for each worker. If the division is not perfect, you may add some "ghost" jobs to have a square matrix. Only one working hour per worker should have an acceptable assignement cost to the ghost jobs. Thus, all workers will work the same time more or less 1 hour. $\endgroup$ – Vince Mar 22 at 15:42
7
$\begingroup$

Since Vince asked me to publish my solution, I decided to write this long post.
Please bear in mind that this code is really really basic and absolutely not optimized, written as fast as possible to perform some test.
Credits for Hungarian algorithm code must be done to vivet.

PURPOSE

I need to create shifts for M workers (variable number each week) on N slots (usually 50 each week, but sometimes some slot could be unavailable).
Each worker can suggest slots he wants to take and others he can't absolutely take and, if possible, these requests should be taken in account.

GENERAL IDEA

Given that creating costs matrix for Hungarian solver can be a pain, I decided (just a quick solution) I can create text files for each worker to report his request and one file for unavailable slots.
All these files must be in the same folder.

FILES STRUCTURE

A single text file must have as many rows as daily slots (usually 10) and as many columns as working days (usually 5).
Each cell must contain a preconfigured char:

  • O means worker really needs that slot assigned
  • o means worker would like to have the slot assigned
  • - means no preference on that slot (it's the default naturally)
  • x means worker would like not to have the slot assigned
  • X means worker can't work on that particular slot

A sample could be

X x - - O
X x - - O
- - - - O
- - - - -
- - - - -
- - - o -
- - - o -
- - - - -
- - - - -
x x x x x 

Unavailable slots file must have a well defined name (always the same) and its content will have the same structure of workers files. Naturally each cell having a value different than - means that slot is not available to workers.

CODE

Source code can be found here.
Unfortunately .NET Fiddle uses framework 4.5, so program can't be compiled and run online due to the fact I use a newer framework (4.7.1).
Also consider my real code is organized into several files!

It works and it's fast, so I'm completely satisfied with this part.

A STEP FURTHER

First problem solved, pretty good. But now I have to face the next one: I have several locations to assign workers shifts to and these locations share the same working hours.
A first attempt was to raise the number of columns on each file: cols 1-10 are for the 1st venue, cols 11-20 for the 2nd and so on.
Code works without any change and Hungarian algorithm processes data in a while, good; but, as expected, I end having overlapping shifts for the same workers on multiple venues (it's random, but always happens).
I could solve this problem by computing 1st venue, then changing each worker requests denying slots already given in the 1st venue before computing the 2nd one; not exactly the best way I'm sure, just an idea I had, and I'm not sure I can always find a solution.

OTHER OPTIMIZATIONS

I could also think about adding other rules (e.g. if possible worker should have max 2 ranges in a day (avoiding for example solutions having slots 0, 2, 4, 6 and 8 and preferring slots 0-2, 6-8 instead) and limits, but this goes too far from the starting question, so it will be something I'm asking in future and I'm quite sure it could need some more complex algorithm or libraries (e.g. ORTools by Google) I'm searching/studying.

$\endgroup$
  • 1
    $\begingroup$ Great. If you want to go further adding new constraints/statements, it would be better to generate a new question making this one a finalized question/answer that anybody can use. The constraints you want to add are likely to make the problem NP-complete in the general case. It begins to be very important to define properly the input dimensions to find a relevant solution. $\endgroup$ – Vince Mar 24 at 12:41
6
$\begingroup$

For the sake of completeness (since Vince has given you good help already, and it seems like you've got a program that works):

This is known as the assignment problem: given some set of workers and some set of shifts, where each worker might have preferences about which shifts they take, how can you find the optimal schedule?

The standard solution to it is called the modified Hungarian algorithm: it wasn't actually developed in Hungary, but it was based on the earlier work of some Hungarian mathematicians. This is the algorithm implemented in the other answer, and it runs in $O(n^3)$ time (though for any practical purposes you won't really have to worry about that aspect).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.