Optimal shift algorithm

Question

I tried for some time to solve the scheduling problem for the pool I was working with. This problem is as follows ...

There are many lifeguards in the pool, each of which has a certain number of hours that they would like to work. We hope to keep the average number of hours from each lifeguard the desired number of hours as low as possible and as fair as possible for everyone. Each lifeguard is also a college student and, therefore, will have a different availability schedule.

Each week the schedule of the event pool is different from the last, so a new schedule must be created every week.

So many rescuers are required for certain time intervals each day (for example, 3 guards from 8 am to 10 am, 4 guards from 10 am to 3 pm and 2 guards from 3 to 10 pm). Here's the hard part. There are no clearly defined shifts (slots) to accommodate each of the rescuers (due to the fact that creating a schedule may not be possible if rescuers are available and the changing schedule of weekly events).

Therefore, the schedule should be created from scratch, only with ...

• Rescuers and their information (number of hours desired, availability)
• The schedule of the pool of events, as well as the number of guards required for duty at any time.

Now the problem can be clearly defined as "Create a possible schedule that covers the required number of guards at any time of the day or week, and be as fair as possible for all rescuers when planning."

Creating a possible schedule that covers the required number of guards at any time of every day of the week is part of the problem, which is necessary and must be completely resolved. The second half of how to be as fair as possible for all rescuers greatly complicates the problem, which makes me believe that I will need an approximate approach, since the possible number of ways to divide a working day can be ridiculous, but sometimes it can be necessary, since only possible a schedule can be ludicrous for justice.

Change One of the most commonly used algorithms that I find is the “Hospitals / Residents” problem, but I don’t think it will be applicable, since there are no clearly defined slots for accommodating workers.

Answer 1

You need to turn your criterion of justice into an objective function. Then you can select any number of workplace planning tools . For example, you describe the need to minimize the average difference between the desired and appointed hours. However, I suggest you consider minimizing the maximum difference. This seems fairer (to me), and it will usually lead to a different schedule.

The problem, however, is a little more complicated. For example, if one guard always closes, and the rest all get the desired watch, this is unfair. Therefore, you can introduce variables into your justice model, which represent the total mismatch for each guard from previous weeks. In addition, a one-hour breakdown for a security guard who wants to work four hours a week may be more unfair than for a security guard who wants to work twenty. To deal with such things, you may need weight differences.

You may need to impose restrictions, for example, so that no more than one hour is assigned, or that each defender has a certain amount of time between shifts or the number of slots assigned to one guard per week should not exceed a certain threshold. Many planning tools have the ability to manage these constraints, but you must add them to the model.

Answer 2

One way to solve this is by using restriction programming - the Wikipedia article contains links for several languages ​​and restriction restriction libraries. Here is an article describing how to use constraint programming to solve planning problems.

Another option is to use the greedy algorithm to search for a (possibly invalid) solution, and then use the local search to make the solution invalid, or to improve the suboptimal greedy solution. For example, start by assigning each lifeguard their preferred hours, which will result in too many guards being planned for some slots, and also leading to an absurd number of hours for some guards; then use local search to not assign guards with the most hours from slots that have too many guards assigned.