Lunch at the 'Tek-Tips' Restaurant

[duncdude]

Hi everyone

I wonder if anyone can help me with this problem. I have been trying - with various levels of success - for a couple of weeks

Basically I would like to write a Perl script that would dynamically create a staff rota for a [red]restaurant[/red] each week

I have a friend - Sophia - who is a manager at a restaurant and she is responsible for this task. I went through the procedure with her and it is not easy by any means!

As an interim I have written an Excel spreadsheet to assist with the task - implementing conditional formatting, etc.
I hope to eventually create a dynamic script that will churn away and come up with the 'best' option - if this is possible... nothing is impossible, right?

The script - to be adaptable - will require the following:-
Variable number of shifts over the week - each shift having a required number of staff [tt]e.g. [blue]@quota = qw(7 7 7 7 7 8 8 8 8 9 9 9 9 7);[/blue][/tt]
This would set up a main loop with 14 shifts, each reflecting the number of staff required
Variable numbers of staff
Staff aptitude scores - once the script has come up with a potential rota these scores can be used to calculate the suitability of the rota
(i.e. if a poor member of staff is on the floor on a Saturday night it will score that far worse than if it was a more competent member of staff)
Definite & Requested days off - requested days off are not necessarily actioned

This is a tabulated example of Sophia's restaurant, with the staff quotas:-

[tt]shift 00 => 7 00 01 02 03 04 05 06 07
shift 01 => 7 00 01 02 03 04 05 06 07
shift 02 => 7 00 01 02 03 04 05 06 07
shift 03 => 7 00 01 02 03 04 05 06 07
shift 04 => 7 00 01 02 03 04 05 06 07
shift 05 => 8 00 01 02 03 04 05 06 07 08
shift 06 => 8 00 01 02 03 04 05 06 07 08
shift 07 => 8 00 01 02 03 04 05 06 07 08
shift 08 => 8 00 01 02 03 04 05 06 07 08
shift 09 => 9 00 01 02 03 04 05 06 07 08 09
shift 10 => 9 00 01 02 03 04 05 06 07 08 09
shift 11 => 9 00 01 02 03 04 05 06 07 08 09
shift 12 => 9 00 01 02 03 04 05 06 07 08 09
shift 13 => 7 00 01 02 03 04 05 06 07[/tt]

I have taken the current listing of MVP's (and others) from the Perl forum and given them all aptitude scores:-
Please don't be offended by the scores - they are not an actual indication of suitability to be a waiter!

PaulTEG[red],100[/red]
rharsh[red],90[/red]
duncdude[red],80[/red]
dchoulette[red],70[/red]
nawlej[red],60[/red]
mikevh[red],50[/red]
TomThumbKP[red],40[/red]
parkers[red],30[/red]
Rieekan[red],20[/red]
MikeLacey[red],10[/red]
ag5t[red],5[/red]
hermes1[red],5[/red]
pwils025[red],5[/red]
rab54[red],5[/red]
timgerr[red],5[/red]
peacecodotnet[red],5[/red]
nix45[red],5[/red]
Ramnarayan[red],5[/red]
Valerie[red],5[/red]
TheGenius22[red],5[/red]

Now i'll output some potential rotas and their scores (the number of people required on the shift is also used in governing the suitability of the member of staff in that slot

It makes more sense visually - here are 3 examples:-
[tt]
00 parkers|30*7 nixFourtyFive|5*7 dchoulette|70*7 rabFiftyFour|5*7 Ramnarayan|5*7 Valerie|5*7 mikevh|50*7
01 hermes|5*7 Rieekan|20*7 pwils|5*7 Valerie|5*7 nixFourtyFive|5*7 rharsh|90*7 dchoulette|70*7
02 ag5t|5*7 nixFourtyFive|5*7 mikevh|50*7 TheGenius|5*7 Rieekan|20*7 nawlej|60*7 Valerie|5*7
03 peacecodotnet|5*7 mikevh|50*7 nawlej|60*7 duncdude|80*7 TheGenius|5*7 pwils|5*7 dchoulette|70*7
04 dchoulette|70*7 Valerie|5*7 MikeLacey|10*7 TomThumbKP|40*7 pwils|5*7 Rieekan|20*7 Ramnarayan|5*7
05 hermes|5*8 MikeLacey|10*8 Valerie|5*8 ag5t|5*8 peacecodotnet|5*8 Rieekan|20*8 nixFourtyFive|5*8 Ramnarayan|5*8
06 ag5t|5*8 Ramnarayan|5*8 TomThumbKP|40*8 rabFiftyFour|5*8 MikeLacey|10*8 Valerie|5*8 rharsh|90*8 Rieekan|20*8
07 TheGenius|5*8 rharsh|90*8 nixFourtyFive|5*8 nawlej|60*8 parkers|30*8 hermes|5*8 mikevh|50*8 rabFiftyFour|5*8
08 dchoulette|70*8 nixFourtyFive|5*8 ag5t|5*8 Ramnarayan|5*8 TheGenius|5*8 nawlej|60*8 duncdude|80*8 pwils|5*8
09 duncdude|80*9 pwils|5*9 parkers|30*9 ag5t|5*9 Rieekan|20*9 Ramnarayan|5*9 nixFourtyFive|5*9 timgerr|5*9 dchoulette|70*9
10 Valerie|5*9 TomThumbKP|40*9 timgerr|5*9 parkers|30*9 Ramnarayan|5*9 nawlej|60*9 mikevh|50*9 MikeLacey|10*9 nixFourtyFive|5*9
11 rabFiftyFour|5*9 Ramnarayan|5*9 parkers|30*9 TheGenius|5*9 Rieekan|20*9 rharsh|90*9 hermes|5*9 timgerr|5*9 nawlej|60*9
12 Valerie|5*9 parkers|30*9 TomThumbKP|40*9 hermes|5*9 Rieekan|20*9 MikeLacey|10*9 pwils|5*9 TheGenius|5*9 dchoulette|70*9
13 pwils|5*7 MikeLacey|10*7 nixFourtyFive|5*7 dchoulette|70*7 ag5t|5*7 Rieekan|20*7 TomThumbKP|40*7
--- attempt 1 => completed --- [red]score 21185[/red] ---

00 pwils|5*7 TomThumbKP|40*7 peacecodotnet|5*7 rharsh|90*7 parkers|30*7 nixFourtyFive|5*7 timgerr|5*7
01 MikeLacey|10*7 dchoulette|70*7 nawlej|60*7 ag5t|5*7 hermes|5*7 timgerr|5*7 Valerie|5*7
02 TomThumbKP|40*7 duncdude|80*7 dchoulette|70*7 hermes|5*7 parkers|30*7 MikeLacey|10*7 nawlej|60*7
03 TheGenius|5*7 Valerie|5*7 MikeLacey|10*7 peacecodotnet|5*7 nawlej|60*7 hermes|5*7 rabFiftyFour|5*7
04 dchoulette|70*7 rharsh|90*7 TomThumbKP|40*7 Valerie|5*7 duncdude|80*7 nixFourtyFive|5*7 rabFiftyFour|5*7
05 rharsh|90*8 rabFiftyFour|5*8 MikeLacey|10*8 peacecodotnet|5*8 mikevh|50*8 nixFourtyFive|5*8 nawlej|60*8 Valerie|5*8
06 ag5t|5*8 hermes|5*8 TheGenius|5*8 parkers|30*8 timgerr|5*8 nawlej|60*8 pwils|5*8 TomThumbKP|40*8
07 parkers|30*8 timgerr|5*8 Valerie|5*8 ag5t|5*8 Ramnarayan|5*8 pwils|5*8 dchoulette|70*8 nawlej|60*8
08 duncdude|80*8 Valerie|5*8 parkers|30*8 hermes|5*8 nawlej|60*8 TheGenius|5*8 ag5t|5*8 Rieekan|20*8
09 peacecodotnet|5*9 Ramnarayan|5*9 parkers|30*9 nixFourtyFive|5*9 dchoulette|70*9 rabFiftyFour|5*9 nawlej|60*9 rharsh|90*9 TomThumbKP|40*9
10 nixFourtyFive|5*9 TheGenius|5*9 nawlej|60*9 duncdude|80*9 rharsh|90*9 Rieekan|20*9 TomThumbKP|40*9 rabFiftyFour|5*9 dchoulette|70*9
11 dchoulette|70*9 hermes|5*9 pwils|5*9 parkers|30*9 rabFiftyFour|5*9 Rieekan|20*9 TheGenius|5*9 mikevh|50*9 Ramnarayan|5*9
12 mikevh|50*9 peacecodotnet|5*9 TomThumbKP|40*9 ag5t|5*9 pwils|5*9 hermes|5*9 Ramnarayan|5*9 rabFiftyFour|5*9 parkers|30*9
13 rharsh|90*7 hermes|5*7 nawlej|60*7 parkers|30*7 timgerr|5*7 dchoulette|70*7 Valerie|5*7
--- attempt 2 => completed --- [red]score 24540[/red] ---

00 mikevh|50*7 nawlej|60*7 Ramnarayan|5*7 Rieekan|20*7 Valerie|5*7 ag5t|5*7 rabFiftyFour|5*7
01 TheGenius|5*7 duncdude|80*7 pwils|5*7 rabFiftyFour|5*7 Valerie|5*7 nawlej|60*7 rharsh|90*7
02 TomThumbKP|40*7 rabFiftyFour|5*7 mikevh|50*7 TheGenius|5*7 nawlej|60*7 pwils|5*7 parkers|30*7
03 mikevh|50*7 TomThumbKP|40*7 Ramnarayan|5*7 nawlej|60*7 nixFourtyFive|5*7 Valerie|5*7 TheGenius|5*7
04 peacecodotnet|5*7 rharsh|90*7 pwils|5*7 Valerie|5*7 TomThumbKP|40*7 timgerr|5*7 MikeLacey|10*7
05 TomThumbKP|40*8 Rieekan|20*8 MikeLacey|10*8 hermes|5*8 dchoulette|70*8 timgerr|5*8 TheGenius|5*8 mikevh|50*8
06 Rieekan|20*8 nawlej|60*8 peacecodotnet|5*8 rabFiftyFour|5*8 parkers|30*8 rharsh|90*8 nixFourtyFive|5*8 timgerr|5*8
07 ag5t|5*8 TomThumbKP|40*8 parkers|30*8 dchoulette|70*8 mikevh|50*8 Valerie|5*8 timgerr|5*8 peacecodotnet|5*8
08 parkers|30*8 dchoulette|70*8 Ramnarayan|5*8 peacecodotnet|5*8 pwils|5*8 nawlej|60*8 TomThumbKP|40*8 MikeLacey|10*8
09 peacecodotnet|5*9 nawlej|60*9 Rieekan|20*9 mikevh|50*9 MikeLacey|10*9 rharsh|90*9 TheGenius|5*9 duncdude|80*9 nixFourtyFive|5*9
10 peacecodotnet|5*9 TheGenius|5*9 timgerr|5*9 TomThumbKP|40*9 nixFourtyFive|5*9 hermes|5*9 nawlej|60*9 rharsh|90*9 dchoulette|70*9
11 duncdude|80*9 rabFiftyFour|5*9 mikevh|50*9 TheGenius|5*9 parkers|30*9 pwils|5*9 timgerr|5*9 ag5t|5*9 Rieekan|20*9
12 parkers|30*9 pwils|5*9 duncdude|80*9 rabFiftyFour|5*9 dchoulette|70*9 TheGenius|5*9 Ramnarayan|5*9 TomThumbKP|40*9 nawlej|60*9
13 MikeLacey|10*7 pwils|5*7 nawlej|60*7 nixFourtyFive|5*7 rabFiftyFour|5*7 mikevh|50*7 timgerr|5*7
--- attempt 3 => completed --- [red]score 24370[/red] ---[/tt]

As you can see the script loops through the shifts - from 0..13 in this case (14 shifts in total - Monday A.M. through to Sunday P.M.)

It then enters another loop - the number of staff required to cover the shift - and takes people from the staff list until the quota ... and then on to the next shift

This is all scored:-
staff member's competency x shift quota - and added up to give a total score for the rota

In theory, after hundreds of thousands of attempts, the highest score should be a very decent rota

But... My method is using random values. This essentially means that someone might never appear on the rota. Unlikely but possible.
Is there a way that each cell could be revolved like a car mileometer? This would mean that EVERY permutation would be covered.

Finally, bear in mind that someone cannot possibly work if they have a definite day off - but could (if necessary) if they have a requested day off

Other things to bear in mind are that it would be nice if no one was doing too many 'double' shifts - for example.
Really this is just common sense. At the end of the day the best rota is the one that evenly shares out the shifts among the members of staff,
puts the strongest members of staff on the more difficult shifts, and takes into account the rules

I know this is a fair bit of information but I can get quite close to a model within a few lines of code - and i'm a muppet!

I'd really appreciate some help on this - it is quite an interesting problem!

My brain is on fire now - if i've made an glaring errors in this post please let me know


Kind Regards
Duncan

 

[iribach]

Duncan
can you please randomly put a \n in
your post, so we can read it without using
the st... horiz-scroll-bar?

 

[duncdude]

Hi Iribach

I'd love to - but this would completely destroy the output which is critical to understanding the problem

shift 0 -> 7 quota person1 person2 person3 person4 person5
person6 person7 person8 person9

... I thought this would look nasty?


Kind Regards
Duncan

 

[PaulTEG]

Dunc,

first off I'm a bit pi553d, that I don't have a shift.

The timetable problem is old one where 95% of the job is done in 5% of the time, it's the last 5% that takes the majority of the time, and headaches, and all the experience of the roster maker.

The problem is that there's too much information that's not explicit (poorly defined variables), in terms of experience, willingness to work extra shifts, seniority, days off, requested days off, training, etc. In the classic timetable problems it's usually a teacher, who has to be in their home room at 10 o'c for roll call, but now they're scheduled to take the fourth form for swimming on a friday morning from 9-11.

As regards keeping track of who's got what rotas, a hash that's dumped to a text file or database might be the answer

$staff{'duncdude'}.="|mondaypm";

so your code could sanity check that each member of the hash, has at least the minimum number of shifts per week, or in the case of part time staff, some will want more minimum shifts per week... see more variables...

It's not easy, and I wish you the best of luck with it, it'll be a saleable commodity when it's up and running

HTH
--Paul

It's important in life to always strike a happy medium, so if you see someone with a crystal ball, and a smile on their face ...

 

[duncdude]

Hi Paul

Thank you for your reply

You didn't get a shift because i'm giving you a week off for being the forum's MVP! Actually it was a VERY basic mistake in my random number selection - i'm very embarrassed! You were at the top of my waiter list... but never got picked!

I completely agree with you. A monkey could probably fill in the majority of the rota - then it starts getting complicated. The repurcussions of earlier entries start causing all sorts of headaches

And one last note - it's very nice to hear positive feedback - and your comment:-

It's not easy, and I wish you the best of luck with it, it'll be a saleable commodity when it's up and running

... gives me the incentive to plough on with this problem! So many people want to look at the negative side and this attitude can be so destructive.

Thanks dude!


Kind Regards
Duncan

 

[PaulTEG]

Dunc,

You may want to start by defining all your data.

Days off, Holidays, Past weeks(extra shifts) to give some negative aspect to the scoring so that the most suitable in the past becomes deselected because they've been so suitable in the past, and also account for upcoming days off, days in lieu etc

Or, you could go at this a completely different way, assume that they all come in for pay day, and they request the shifts they're willing to work (even through a web form), after talking amongst themselves to avoid as many conflicts as possible, and then your program kicks in to resolve overbookings in a fair and equitable manner, based on history gathered - but for this to work you'll need previous trends, cause it'lll just tee people off to start from an arbitrary point

--Paul

It's important in life to always strike a happy medium, so if you see someone with a crystal ball, and a smile on their face ...

 

[duncdude]

Hi Paul

I totally agree with you about defining the data beforehand. However, at present, I don't think I want to involve too many factors - there is quite a high staff turnover so i'm not too concerned with past shifts, etc. From talking with Sophia I understand that each week is treated individually. I would like, as you suggest, to immediately reflect definite days off - and reject immediately should a person be put into a shift that they cannot do - they could be leaving mid-week for instance. The script would score negatively - although not reject - in the case of requested days off - as you mention in your post

As I have been writing this I have just had this thought - other than the 'days off' i think it would be best at present to ignore any 'rules' whatsoever

How does this sound for a 'summary'...

The restaurant does, will or is likely to experience all sorts of annoying staff requests - therefore:-

1 - mark definite days off
2 - mark requested days off
3- share the remaining shifts as equally as possible with the remaining staff

Elaborating slightly:- Lets say there are 110 'slots' in total. There are 20 staff. This would mean 5.5 shifts each. At the end of compiling a suggested rota the script computes the 'average' (fairest) shift quota. It then adds up all the differences and totals them up. If you had 8 shifts, for example, the script would compute 8 - 5.5 = 2.5. This would be totalled for each staff member - the rota with the lowest deviance from zero would be the best. How does that sound?

Then, if anyone wants to swap shifts, they can. They just need to clear it with a manager

Let me know your views

Many thanks Paul


Kind Regards
Duncan

 

[PaulTEG]

Dunc,

5.5 shifts - don't know how a half shift could be represented, some people would have to be 5, the rest 6, and rotate them the following week.

As regards no rules, I think that's a mistake in light of that which is what you're trying to accomplish - a rules based rostering system.

Can you post a url for test?

--Paul

It's important in life to always strike a happy medium, so if you see someone with a crystal ball, and a smile on their face ...

 

[duncdude]

Monday Tuesday Wednesday Thursday Friday Saturday Sunday
26-Jul 27-Jul 28-Jul 29-Jul 30-Jul 31-Jul 1-Aug
# days # nights [days] [*2] [total] [off] a.m. p.m. a.m. p.m. a.m. p.m. a.m. p.m. a.m. p.m. a.m. p.m. a.m. p.m.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Mary 2 2 5 1 6 2 1 1 1 1 1 1 ! ! ! !
Michelle 2 2 5 1 6 2 1 1 R 1 1 1 1
Yasmin 2 2 5 1 6 2 1 1 1 1 R R 1 1
Joanne 2 3 5 0 5 2 1 R 1 1 1 1 ! ! ! !
Ania 2 3 5 0 5 2 R R R R 1 1 1 R 1 1
Bash 4 0 5 1 6 2 ! ! 1 ! ! 1 1 1 1 1
Bryony 1 3 5 1 6 2 R R 1 1 1 1 1 1
Katie 2 2 5 1 6 2 1 1 1 1 1 1 R R
Kristin 2 2 5 1 6 2 ! ! 1 1 1 1 1 1 R R R
Marina 2 3 5 0 5 2 R R 1 1 R 1 1 1 R R
Sara 3 2 5 0 5 2 1 1 1 1 1
Spikey 2 2 5 1 6 2 1 1 1 1 1 1
Clyde 3 2 5 0 5 2 1 1 1 1 1
Lucy 4 1 5 0 5 2 1 1 1 1 1
Simon 2 2 5 1 6 2 1 1 1 1 1 1
Ann 2 2 5 1 6 2 1 1 1 1 1 1
Myla 2 2 5 1 6 2 1 1 1 1 1 1
Joe 2 3 5 0 5 2 1 1 1 1 1
Dan 2 3 5 0 5 2 1 1 1 1 1
Jolene 2 3 5 0 5 2 1 1 ! 1 1 1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
quota -> 7 7 7 7 8 8 8 8 8 9 9 9 9 7
actual -> 7 7 7 7 8 8 8 8 8 9 9 9 9 7


Kind Regards
Duncan

 

[duncdude]

Hi Paul

If you can copy/paste & use a monospaced font you'll see this weeks rota

As you state - some 5 days, some 6

By no rules - I think I mean [bfew rules[/b] - I think a problem would be, for instance, if you had been given 5 shifts, then next week the script wants you to have 6 - then you leave...
what a headache!

I'd rather, if it is possible, just have the script do some simple maths

thinking about the problem in a different way:-

i.e. 110 'staff' are required (7 + 7 + 7 + 7 + 7 + 8 + 8 + 8 + 8 + 9 + 9 + 9 + 9 + 7 = 110)

how about pre-preparing the staff by grabbing all 20 staff and putting the names into an array - then again and again until it exceeds the quantity. Then remove random staff - or the least competent - or the staff who have worked the shortest time - until we have the required number

... then to fill in the gaps ...


Kind Regards
Duncan

 

[PaulTEG]

Dunc,
kinda hard to read
--Paul

It's important in life to always strike a happy medium, so if you see someone with a crystal ball, and a smile on their face ...

 

[duncdude]

It shouldn't be if you set the tab stops to about 10 spaces


Kind Regards
Duncan

 

[PaulTEG]

Dunc, please post in code tags, the spaces are hard coded  s

--Paul

It's important in life to always strike a happy medium, so if you see someone with a crystal ball, and a smile on their face ...

 

[duncdude]

this is the other approach - and it's nasty (I think)

i'll refer to the cells as x,y co-ordinates:-

think of each one of the slots as a 20-sided dice
[tt]
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7
1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7
2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7
3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7
4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7
5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8
6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8
7.0 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8
8.0 8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8
9.0 9.1 9.2 9.3 9.4 9.5 9.6 9.7 9.8 9.9
10.0 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9
11.0 11.1 11.2 11.3 11.4 11.5 11.6 11.7 11.8 11.9
12.0 12.1 12.2 12.3 12.4 12.5 12.6 12.7 12.8 12.9
13.0 13.1 13.2 13.3 13.4 13.5 13.6 13.7[/tt]

rotate 0.0 from the 1st through last member of staff. once it has done 1 full circle then increment 1.0 by 1 name. Then back to 0.0 for another full circle. this is like a speedometer of a car. the maths is frightening. however, MOST of the guesses would be totally ridiculous. It would - in theory - start with every cell being Paul and the last attempt - hundreds of millions of iterations later - every cell would be TheGenius. o.k. - this is crazy in many respects - but at least it is very simple in its construct. can this be done?


Kind Regards
Duncan

 

[duncdude]

Paul - I'm a muppet! To check it would be O.K. I copied & pasted from the 'Message' window - it hasn't had a chance to convert the tabs at that point... I do apologise!


Kind Regards
Duncan

 

[duncdude]

Paul - I'm a muppet! To check it would be O.K. I copied & pasted from the 'Message' window - it hasn't had a chance to convert the tabs at that point... I do apologise!

This might be easier:-

http://www.my-mot.co.uk/tek-tips/Paul_rota.xls

Kind Regards
Duncan

 

[PaulTEG]

Dunc,

I'm not realy sure what the nice Excel sheet is to represent

send me a mail on p_teggart@nospam.hotmail.com

It's important in life to always strike a happy medium, so if you see someone with a crystal ball, and a smile on their face ...

 

[duncdude]

Hi Paul

The Excel sheet was just an interim measure. It simply allows Sophia to fill in a '1' in any cell (shift) where she would like a member of staff to work. The Excel functions total the days/nights/total shifts/days off - to take the cross-referencing required out of the task. It also colours up cells red when an exclamation mark is entered - definite shift off - or yellow when an 'R' is entered - requested shift off. The totalling takes place on the left hand side of the sheet. The column totals are:-

1. day shifts worked
2. night shifts worked
3. days worked (you could work a day, or a night, or a double shift - all are classed as one 'day'
4. double shifts worked
5. total shifts worked
6. total 'days' off - everyone should ideally have 2 whole days free

Cheers


Kind Regards
Duncan

 

[duncdude]

19,298 members on the Perl forum and Paul is the only kind dude to offer me some help!?

:-(


Kind Regards
Duncan

 

[PaulTEG]

up to me eights at the mo'

--Paul

It's important in life to always strike a happy medium, so if you see someone with a crystal ball, and a smile on their face ...