Optimal holiday plan for employees

Question

Suppose our company has 12 employees and that each is allowed to take a 3-week vacation over a period of 8 weeks. Can we get an optimal combination, i.e., we have as many employees as possible ready but every single employee takes his or her 3 weeks?

Answer 1

If "optimised" means "the day with fewest employees at work should have as many employees as possible", and vacations are required to be three consecutive weeks, then I think your best bet is to make four overlapping batches (one starting in the beginning of the first week, one in the beginning of the second or third, one beginning in the beginning of the fourth or fifth, and one beginning in the beginning of the sixth week). Then send three employees on vacation each batch.

That way, only two batches overlap at any time, and you have at least half of your employees on call each day (not counting sick leave or similar). I don't think you can get five batches without triple overlap somewhere.

If you can distribute single weeks, then you can get more people on site at any time. For instance, consider having a list of the employees, and the first week give vacation to the first five on the list. The next week to the next five, and so on, looping around when you reach the bottom. Then you have seven employees on call every day, and the last of the eight weeks you even have eleven employees on call, so you can make up for that by giving only four employees vacation some of the weeks (four of the weeks, in fact, with five employees the other four).

Of course, once you have used this scheme to decide who takes vacation simultaneously each week, you can shuffle the weeks themselves around so that the employees get more consecutive vacations (you can guarantee at least one two-week vacation to all of your employees, and a three-week to some).

Since there are a total of $3\cdot 5\cdot 12 = 180$ vacation days you need to give to your employees, and only $8\cdot 5 = 40$ days to distribute them on, you cannot get away with only giving vacation to four employees at a time, even by giving single days of vacation. You need at least five employees to have vacation simoltaneously some of the time (otherwise you can only reach a total of $160$ vacation days). So this is the best possible.