[Buckie]

Hello bright minds! I've recently started on a project to help somebody to track employee shifts data in a database in FileMaker Pro. And while the database itself is going just fine, nothing fancy here I wanted to take it further just because the improvement I have in mind is exciting to implement.
I'm not familiar with advanced mathematics so I will need more down to earth explanations. In a way this call for help is almost like saying "do this for me" and I'm sorry about that, but it's a very interesting problem to tackle nonetheless.

So with all that out of the way here's what I'm looking to implement:
We have a table with columns of days in a given month and rows of employee names. We need to fill the matrix with day and night shift data so that
- the total number of shifts per person per month is ideally 15 (but can be up to 17)
- there are always 4 persons on a day shift and 3 persons on a night shift per day (this is strict)
- no double shifts (i.e. no night shifts immediately following day shifts and no day shifts immediately following night shifts)
- there may be reserved days for certain employees when they can't go on a shift due to personal reasons (those days will be specially marked in the database)
- certain persons have strict pre-defined schedules that are manually input in the database beforehand (for example, a 10-day series of consecutive day shifts followed by vacation days)
- certain persons would want strictly day shifts or night shifts for the entire month

In other words, the solution should check every unmarked cell and find out whether it should be marked according to the preexisting (pre-filled) data.
I've attached a sample table that we use, it's filled by hand by a manager so it should give a visual idea of what I'm talking about. Don't mind the numbers much, the table usually requires manual tweaking afterwards to allow 5 days shifts for example or more than usual shifts per month for a particular person and so on. Ideally the number of specified shifts per person per month should be handled by the solution as well.

So is this even possible? Any clues are greatly appreciated!
 table.pdf (29.72K)
Number of downloads: 21

[Schrödinger's hat]

Buckie, on 2 February 2012 - 07:59 PM, said:

Hello bright minds! I've recently started on a project to help somebody to track employee shifts data in a database in FileMaker Pro. And while the database itself is going just fine, nothing fancy here I wanted to take it further just because the improvement I have in mind is exciting to implement.
I'm not familiar with advanced mathematics so I will need more down to earth explanations. In a way this call for help is almost like saying "do this for me" and I'm sorry about that, but it's a very interesting problem to tackle nonetheless.

So with all that out of the way here's what I'm looking to implement:
We have a table with columns of days in a given month and rows of employee names. We need to fill the matrix with day and night shift data so that
- the total number of shifts per person per month is ideally 15 (but can be up to 17)
- there are always 4 persons on a day shift and 3 persons on a night shift per day (this is strict)
- no double shifts (i.e. no night shifts immediately following day shifts and no day shifts immediately following night shifts)
- there may be reserved days for certain employees when they can't go on a shift due to personal reasons (those days will be specially marked in the database)
- certain persons have strict pre-defined schedules that are manually input in the database beforehand (for example, a 10-day series of consecutive day shifts followed by vacation days)
- certain persons would want strictly day shifts or night shifts for the entire month

In other words, the solution should check every unmarked cell and find out whether it should be marked according to the preexisting (pre-filled) data.
I've attached a sample table that we use, it's filled by hand by a manager so it should give a visual idea of what I'm talking about. Don't mind the numbers much, the table usually requires manual tweaking afterwards to allow 5 days shifts for example or more than usual shifts per month for a particular person and so on. Ideally the number of specified shifts per person per month should be handled by the solution as well.

So is this even possible? Any clues are greatly appreciated!
table.pdf

Yes, this is certainly possible.
Thinking about it briefly, the vague form of a completely naive algorithm (basically just brute force it) that would do it in roughly time comes to mind.
This would be between somewhat and completely impracticle for more than 50 people. There are probably many improvements that anyone competent would think of along the way, but in general it would still scale horribly.

I don't know the techniques used to do it quickly, though I know they exist.
A good starting point may be to look into integer or linear programming and the associated mathematics. If this is a problem that falls in this domain (and it smells rather similar, I have seen linear programming stuff on a crossword solver) then this would likely be the best approach.
Expect a fair deal of linear and other abstract algebras. So it may be fairly heavy going.

Other approaches/fields that come to mind would be pathing or chess playing algorithms.

This post has been edited by Schrödinger's hat: 2 February 2012 - 08:36 PM

[John Cuthber]

Pretend it's the "latest puzzle game from Japan" and give it to someone who likes sudoku and kakuro.

[Buckie]

Schrödinger's hat,Yes, the brute force idea was the first that came to mind actually. So basically just fill it with random data until it clicks into place? There are about 15 people in total so it should be doable. And thanks for the clues on the fields to research/apply!

John,
great! outsourcing it to Japan is another way to do it! I presume everybody likes sudoku and kakuro there.

[Schrödinger's hat]

Buckie, on 3 February 2012 - 07:09 AM, said:

Schrödinger's hat,Yes, the brute force idea was the first that came to mind actually. So basically just fill it with random data until it clicks into place? There are about 15 people in total so it should be doable. And thanks for the clues on the fields to research/apply!

John,
great! outsourcing it to Japan is another way to do it! I presume everybody likes sudoku and kakuro there.

Ever so slightly more refined than that.
Start with your most constrained employee, and work towards one that can take the most shifts.
That way you're less likely to have to backtrack.

Bear in mind that the work required for this kind of approach increases extremely quickly with number of employees/shifts, so your client may turn around and wonder why their system hangs for 3 hours every morning if they get a few new staff and want you to fix it.

This post has been edited by Schrödinger's hat: 3 February 2012 - 10:59 AM

[Buckie]

Well, it wasn't that hard. There was one important thing that I initially missed - it's that we have strictly 4 day shifts and 3 night shifts. So instead of filling everything totally at random I started filling the table column by column to have days and nights in random places for our 14 employees per day. So the algorithm goes from record #1 to record #15 and puts "D" or "N" in a random place and then goes on and on all the time minding the total number of each type of shift for that given day. Then it proceeds to fill the next day minding the previous day's shift data (so we don't have "ND" shifts). I've also implemented a simple bias system for employees where randomly generated "D" or "N" are biased by an index number in the employee record. So for example if the bias number is "1" then only "N"s are selected and the closer the number to zero, the less nights that employee is going to receive. Nice!
One thing I'm still struggling to overcome is a large discrepancy between total number of shifts per month per employee. After auto-filling some might get 23 shifts per month while others as low as 9. The numbers obviously change and sometimes the difference isn't too big but it's still unacceptable. It happens because the generated pattern in the table is very random - lots of visually contiguous empty spaces and shifts may be clumped together. I'm looking to add more order into the algorithm but don't know where to start. Right now I generate the row to stop on (to place a day or night shift in) by looping through records until Round ( Random * 10 ) = Round ( Random * 10 ). Not optimal perhaps but it does make random stops. Any suggestions to organize the noise a bit?
PS Currently filling the table with 30 days and 14 employees takes about 20 seconds.

Just got that last one figured out too by using another bias index (If ( Random ) > bias...) for checking whether there should be added a new shift for the employee if he was already assigned a shift yesterday. Closer to one will yield a more 'uniformly' filled table while closer to zero will create more lumps.

[ewmon]

I developed an Excel spreadsheet to generate random schedules for people, but that was random delivery routes involving several constraints. A driver might go to clients A, B, C and D one day and go to clients A, B, E, F and G the next day, but it was all within the same shift and took approximately the same amount of time (one of the constraints).

From a human perspective, your employees would love you, the company and their work more if you could:

Assign them to a shift on a weekly basis, so they can schedule their personal life around their work.

• You are scheduling people to work about half the days in a month, and who would want to get stuck working D_N_D_N_D_N_... or don't have two days off in a row (a "weekend") just because a computer generated a random schedule that's supposedly "fair"?
  
• People have families, hire babysitters, share duties, etc. The employee or his/her spouse might share picking up the kids at school/daycare, etc — so it makes life easier if everyone knows that it's their turn or their spouse's turn to do something on a weekly basis rather than a daily basis. Then you could develop the schedules 4 or 5 weeks at a time.

Add constraints about day/night balance per employee, at least on a monthly basis, and perhaps throughout their employment.

• You probably don't want employees complaining to you that they've been stuck with a lot of night shifts for the last few months, while other people have received a lot of day shifts. Some people are especially sensitive about Friday and Saturday nights.
  
• You don't want the perception of favoritism among employees (even though it's actually random) because that'll bring down company morale and productivity fast.

Add constraints about consecutive days. It's not nice if someone must work 10 or 15 days at a stretch (even though they might end up with several consecutive days off at other parts of the month). This includes a constraint about consecutive days among consecutive months. Which reminds me, the no Night-then-Day constraint must be satisfied among consecutive months so no one works the night shift on the last day of one month and the day shift on the first day of the next month.

[Buckie]

ewmon, thanks for the insight. Your post had really got me thinking about that. It was one of the problems I didn't approach because I had no idea on how to organize shifts in a 'humane' way. Implementing constraints for day/night shifts per month per employee is surely a valid idea but I'm not sure exactly how to implement that programmatically. It would need balancing on the rows and I'm filling it by columns, got to think more about how that could be done. The problem of ND shifts on month borders has already been solved as I'm always looking into the last day of the previous month to figure out what to place for the 1st.

I'd really appreciate if you could elaborate more on how to best fill the table. It's not clear what you mean by 'assign them to a shift on a weekly basis', do you mean we shouldn't plan the shift table for a whole month but instead for just one/two weeks? It would be very helpful if you could provide a sample row of 'ideal' shifts how you see it (day 1-31) so I could study that example. Also, I've noted your point about weekends and that is something that should also be implemented in employee's preferences.

[ewmon]

Buckie, on 5 February 2012 - 08:44 AM, said:

ewmon, thanks for the insight. Your post had really got me thinking about that. It was one of the problems I didn't approach because I had no idea on how to organize shifts in a 'humane' way. Implementing constraints for day/night shifts per month per employee is surely a valid idea but I'm not sure exactly how to implement that programmatically. It would need balancing on the rows and I'm filling it by columns, got to think more about how that could be done. The problem of ND shifts on month borders has already been solved as I'm always looking into the last day of the previous month to figure out what to place for the 1st.

I'd really appreciate if you could elaborate more on how to best fill the table. It's not clear what you mean by 'assign them to a shift on a weekly basis', do you mean we shouldn't plan the shift table for a whole month but instead for just one/two weeks? It would be very helpful if you could provide a sample row of 'ideal' shifts how you see it (day 1-31) so I could study that example. Also, I've noted your point about weekends and that is something that should also be implemented in employee's preferences.

Shift fairness.

The day/night fairness might be computed using ratios. If a day shift counts as a "1", and a night shift counts as a "2", then the average would be 1.5, with an allowable range of, say, 1.4 to 1.6. Or it might be computed as the difference between number of day shifts and night shifts for an employee, so that an employee is only allowed to work, at most, three more nights than days or three more days than nights.

These ratios or differences might be calculated (and limited) for the entirety of their employment with you, so for example, an employee who is consistently assigned 3 more night shifts than day shifts per month (allowed by the algorithm) doesn't end up unfairly working 36 more nights than days in a 12-month period (although very improbable). There would be a yearly calculating/limiting whatever "shift fairness" figure-of-merit you choose to use.

A weekly basis.

I meant give someone all day shift or all night shift for the days they work in a week, so they can plan their whole week around that schedule (knowing they'll be working days or nights that week, instead of a crazy mix). You could plan for an entire month (or two, if you wanted), but in increments of weeks, so that's where I got the 4 to 5 weeks at a time comes from.

[khaled]

You can do it the brute force way, which is NP (takes huge amount of time),

But if you want to do it the smart way, you can use Intelligent Search, Dynamic Programming, or Combinatorial Constraint Satisfaction

[imatfaal]

khaled, on 13 February 2012 - 08:10 PM, said:

You can do it the brute force way, which is NP (takes huge amount of time),

But if you want to do it the smart way, you can use Intelligent Search, Dynamic Programming, or Combinatorial Constraint Satisfaction

Just out of curiosity - how do you know it is NP?

Bruteforcing an answer (ie any answer) would seem to me to be polynomial at worse - bruteforcing some "best" answer (with as yet unknown ways of judging merit) might be more likely to be NP - but even so I didn't think anyone could just look at a problem and tell (ie thats half the problem). Or are you able to reduce it to an NP problem?

[khaled]

imatfaal, on 14 February 2012 - 11:41 AM, said:

Just out of curiosity - how do you know it is NP?

Bruteforcing an answer (ie any answer) would seem to me to be polynomial at worse - bruteforcing some "best" answer (with as yet unknown ways of judging merit) might be more likely to be NP - but even so I didn't think anyone could just look at a problem and tell (ie thats half the problem). Or are you able to reduce it to an NP problem?

Despite how trivial scheduling problems may sound,

To be specific, it's NP-hard .. it's a variation of NSP (Nurse Scheduling Problem)

It's usually solved using Constraint Programming or Heuristic Search

This post has been edited by khaled: 28 February 2012 - 03:37 PM

[imatfaal]

Khaled

Two things - the question was not optimization, but finding one simple answer; as there seem to be no minor constraints then I think this makes a difference. And I know about the Nurse Scheduling Problem - and I thought at present it was still assumed to be NP-Hard, but not shown to be NP-hard (ie it has not been reduced to a known NP complete in polynomial time). I am not saying it definitely isn't NP - I was curious why you were certain it was

[khaled]

imatfaal, on 28 February 2012 - 06:29 PM, said:

Khaled

Two things - the question was not optimization, but finding one simple answer; as there seem to be no minor constraints then I think this makes a difference. And I know about the Nurse Scheduling Problem - and I thought at present it was still assumed to be NP-Hard, but not shown to be NP-hard (ie it has not been reduced to a known NP complete in polynomial time). I am not saying it definitely isn't NP - I was curious why you were certain it was

It's good to be curious and it's good to think about it,

These types of problems were already proven NP-Hard in the literature .. and since it can be solved by Constraint Programming,
you can see that it can be reduced to the SAT problem, that how you can know it's NP-Hard,

I think you should avoid using "optimization" in the context of Algorithms since it has a special meaning, I think what you wanted to say
is that the question wasn't about finding an optimal algorithm to solve this problem, but a simple one

Simple answers are a waste of time, either use patterns that may not work, or brute force for years to get the schedule,

I think a simple answer would by reducing the problem to a simpler one that can be solved using Dynamic Programming

[Schrödinger's hat]

khaled, on 28 February 2012 - 09:30 PM, said:

It's good to be curious and it's good to think about it,

These types of problems were already proven NP-Hard in the literature .. and since it can be solved by Constraint Programming,
you can see that it can be reduced to the SAT problem, that how you can know it's NP-Hard,

That's how you know it is at most NP-Hard.
This in no way says anything about whether it is at least NP-Hard.
If I manage to find a way to turn integer comparison into the SAT problem, that doesn't mean it suddenly becomes NP-Hard. It just means I have a horrible algorithm for integer comparison.

Quote

I think you should avoid using "optimization" in the context of Algorithms since it has a special meaning, I think what you wanted to say
is that the question wasn't about finding an optimal algorithm to solve this problem, but a simple one

The meaning of optimization in this context was quite clear.
Imatfaal -- There are constraints here that make me question whether it's polynomial time in the simplest solution. The day may be multiple shifts, people have days off, you don't want to be too inconsistent with number of hours for each person, and so on.
Complicated enough that treating it mathematically would be hard.

Quote

I think a simple answer would by reducing the problem to a simpler one that can be solved using Dynamic Programming

Now that's a sensible answer.

[khaled]

Schrödinger, on 29 February 2012 - 03:15 AM, said:

That's how you know it is at most NP-Hard.
This in no way says anything about whether it is at least NP-Hard.
If I manage to find a way to turn integer comparison into the SAT problem, that doesn't mean it
suddenly becomes NP-Hard. It just means I have a horrible algorithm for integer comparison.

If you read the links, it shows how scheduling problems are intractable & NP-Hard, how to find that an NP problem is
NP-Hard, what is SAT problem, what Optimization means in general context, and Dynamic Programming (Linear Optimization
through optimal solutions over few variables, which result in the optimal solution for the problem)

- Wikipedia:NSP

- Wikipedia:NP

- Wikipedia:NP-Hard

- Wikipedia:Turing Reduction

- Wikipedia:Optimization

- Wikipedia:Dynamic Programming

This post has been edited by khaled: 29 February 2012 - 10:48 PM

[Schrödinger's hat]

Khaled.
This is not the nurse scheduling problem.
At the easiest, everyone is available for every shift, and so finding a solution is very simple.
At the hardest, it closely resembles the nurse scheduling problem, and so finding a solution would be roughly equivalent and take about the same amount of time.

[khaled]

Schrödinger, on 29 February 2012 - 11:38 PM, said:

Khaled.
This is not the nurse scheduling problem.
At the easiest, everyone is available for every shift, and so finding a solution is very simple.
At the hardest, it closely resembles the nurse scheduling problem, and so finding a solution would be roughly equivalent and take about the same amount of time.

Is it that you disagree with me, or won't go read the references .. what I wrote in my reply is no opinion,

A problem is not P or NP, intractable or tractable based on what we think .. NSP is like any scheduling problem,

we just consider them nurses, they can be anything else, with any other constraints .. finding a solution for

scheduling problem might sound simple if you try it on paper, but it's not easy for a computer to solve

[imatfaal]

khaled, on 1 March 2012 - 12:01 AM, said:

Is it that you disagree with me, or won't go read the references .. what I wrote in my reply is no opinion,

Quote

Like many scheduling problems this problem appears to be NP-hard.

vs

Quote

These types of problems were already proven NP-Hard in the literature

First from your citation and second from your post - they are not the same

Quote

A problem is not P or NP, intractable or tractable based on what we think .. NSP is like any scheduling problem,

Clearly not - some scheduling problems are solved easily and others become rapidly and non-deterministically more complicated and time consuming to solve. By saying this problem is NP-hard you are saying that it is at least as hard as any NP-complete problem (ie any NP complete can be reduced to it in polynomial time) and that just doesn't seem to be the case. On a more general matter, If you have a cite I am quite prepared to believe that some formulations of the nsp are np-hard - they have the hallmarks, but I do not believe that this has been shown in general or for the canonical problem.

Quote

we just consider them nurses, they can be anything else, with any other constraints .. finding a solution for
scheduling problem might sound simple if you try it on paper, but it's not easy for a computer to solve

the changing of constraints is non-trivial - in fact it is crucial; there is also the matter of minor and major constraints, which this problem does not deal with.

[khaled]

1. My citation was from Wikipedia, not from Literature

2. The word "Nurse" in NSP, is like "Salesman" in TSP .. they are just a name, each of these problems are just variations of the same problem
and my speak earlier was general about scheduling problems (variations of NSP).

3. I didn't say that NSP is NP-hard, I said scheduling problems are NP-Hard, they can be reduced to CSP\SAT

imatfaal, on 1 March 2012 - 06:20 PM, said:

Quote

we just consider them nurses, they can be anything else, with any other constraints .. finding a solution for
scheduling problem might sound simple if you try it on paper, but it's not easy for a computer to solve

the changing of constraints is non-trivial - in fact it is crucial; there is also the matter of minor and major constraints, which this problem does not deal with.

-- I was talking about the intractability of scheduling problems, not the scheduling constraints

This post has been edited by khaled: 1 March 2012 - 09:49 PM