0

I'm writing a program to brute-force a schedule for my job based on restrictions and certain parameters. To see if brute-forcing the schedule is even feasible, I decided to first calculate the total possible number of schedules based on the parameters:

  • nEmployees - The number of employees
  • nShifts - The number of shifts required per day
  • nDays - The total number of days in the rotation to calculate for

For the sake of simplicity, and to get the worst-case-scenario, I'm not exluding from the calculation schedules that violate labour laws, or are otherwise impossible (like having one person work every shift for the entire rotation).

For our situation specifically, here are the parameters I want to use:

  • nEmployees = 18
  • nShifts = 6
  • nDays = 90

Thinking back to this subject from years ago, my first thought was to just multiply all the numbers together. This only gave me 9720 though, which seems very low; intuitively, I was expecting a much higher number.

Then I realized that if I recall correctly, this gives me the number of schedules where order doesn't matter. The order of the days does matter though, but it doesn't make any sense for the order of shifts or people to matter; Person1 working Shift1 and Person2 working Shift2 is the same as Person2 working Shift2 and Person1 working Shift1.

I think this leaves me with something like $nDays^{nShifts*nEmployees}$ (from memory). That gives me a massive result though, so I hope that's incorrect.

Is this the correct formula?

Carcigenicate
  • 339

1 Answers1

2

That's not exactly correct. You've actually underestimated.

There are nShifts*nDays distinct slots you need to fill, and nEmployees which can go in each slot. Therefore there are $nEmployees^{nShifts*nDays}$ possible combinations.

Intuitively, think of picking an employee for the first shift of the first day -- the the second shift of the first day... and so on. You'll end up repeating this nShifts*nDays times, and each time you're multiplying by nEmployees.

The reason nDays is in your exponent and not base is because you're multiplying the number of assignments for every day.

The reason you can't multiply nEmployees and nShifts is because that only counts the ways to pick one shift and one employee to fill it.

shimao
  • 202
  • If I translated it right, I got an answer so long that it exceeds what I can fit in a comment here. I also calculated how many years it would take assuming 1 schedule a millisecond, and it too exceeds the comment length. So, that seems to be completely unfeasible, unfortunately. Back to the drawing board :/. Can you give me some terms to lookup, or explain how you got the equation that you did? Thank you. – Carcigenicate Aug 10 '15 at 22:46
  • @Carcigenicate I had an error in my answer which I've fixed now -- try to see if it makes any more sense now – shimao Aug 10 '15 at 23:05
  • The new equation looks almost like mine. You're sure this new one is correct? – Carcigenicate Aug 10 '15 at 23:08
  • @Carcigenicate Yes. Think of it as counting the number of possible passwords. Your alphabet, in this case nEmployees, goes in the base, and the length, in this case nShifts*nDays, goes in the exponent. – shimao Aug 10 '15 at 23:15
  • Ok, thanks. Ill recalculate it. I can't tell off the top of my head if it's better or not. – Carcigenicate Aug 10 '15 at 23:18
  • Aww, your new equation is "worse" :(. Thanks for the help anyway. – Carcigenicate Aug 10 '15 at 23:34