How to make an optimal schedule

[daniel_i_l]

Let's say I have a group of people and 7 different jobs that have to be done every week - one per day. Each job requires one person. How do I distribute the jobs among the group so that both the "vacation time" between each workday and the time between doing the same job twice is constant throughout the group?
In other words, I need an even distribution of both workdays in general and of specific jobs.
What tools are used to solve this kind of problem?
Thanks.

 

[benorin]

If it doesn't matter what day a particular job is done, but rather only that each job be done once per week and exactly one job be done per day, then let the jobs be denoted j1, j2, ..., and j7. Let us further muck things up by assuming that we have exactly 7 people in our work pool, conveniently named p1, p2, ..., and p7.

Now, as a trivial solution we may have p1 work day 1 of the week (Sunday if you wish), have p2 work day 2 of the week, ..., and have p7 work day 7 of the week so that the time betwixt work days for each person in the work pool is a constant (as it happens, 6 days for every person). The job assignments the initial week could be: j1 is done by p1 on day 1, j2 is done by p2 on day 2, generally: jk is done by pk on day k for 1 <= k <= 7. Now that p1 works day 1, and p2 works on day 2, and so on we will leave fixed (for simplicity) and permute the job assignments by 1 each week to induce a 7 week cycle.

Hence, during week 2, p1 does j2 on day 1, p2 does j3 on day 2, and so on... up to p6, who does j7 on day 6, and, p7 who does j1 on day 7.

Hence, during week 3, p1 does j3 on day 1, p2 does j4 on day 2, and so on... up to p5, who does j7 on day 5, and, p6 who does j1 on day 6 followed by p7 who does j2 on day 7.

You get the idea, by week 8, the job assignments are back to same as the initial week, establishing a constant time interval between each worker doing the same job twice (7 weeks, same for each worker and the particular job being done again).

I'll stop being lazy and do the table:

[tex]\text{Values of } k \text{ are specified in the first row.}[/tex]
[tex]\text{Each column then represents } p_k \text{ working on day } k \text{ doing the job listed in that column during the week indicated by row}[/tex]

[tex]
\begin{array}{l|c|c|c|c|c|c|c} \text{ }\, \, \, k= & 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline \text{Week 1} & j_1 & j_2 & j_3 & j_4 & j_5 & j_6 & j_7\\\hline \text{Week 2} & j_2 & j_3 & j_4 & j_5 & j_6 & j_7 & j_1\\\hline \text{Week 3} & j_3 & j_4 & j_5 & j_6 & j_7 & j_1 & j_2\\\hline \text{Week 4} & j_4 & j_5 & j_6 & j_7 & j_1 & j_2 & j_3\\\hline \text{Week 5} & j_5 & j_6 & j_7 & j_1 & j_2 & j_3 & j_4\\\hline \text{Week 6} & j_6 & j_7 & j_1 & j_2 & j_3 & j_4 & j_5\\\hline \text{Week 7} & j_7 & j_1 & j_2 & j_3 & j_4 & j_5 & j_6\\\hline \text{Week 8} & j_1 & j_2 & j_3 & j_4 & j_5 & j_6 & j_7\\\end{array}

[/tex]​

.

Non-trivial solutions and possibly unsolvable scenarios could arise for other particular values of the number of people in the work pool. On a hunch, I would recommend trying some sort of group theory (maybe just modular arithmetic) to solve for every class of solution.

Also, it was not clear if the two constants required for a viable schedule were allowed to vary from worker to worker or from job to job versus requiring the same vacation time for every worker. (Consider, 4 part-time workers p1a, p1b, p7a, and p7b working the week-ends where the a's work odd weeks and the b's work even weeks having a 14 day vacation constant and a repeat job every 16 weeks while the other 5 full-time workers have the same constants as the they did in the table.

I could go on, and on... but I spare you.

Ben