Scheduling problem. Get most workers pe shift based on times available.

Question

I'm trying to fill a work schedule with three shifts.

Lets say I have a list of people. Each person tells me A) Which of the three shifts they are available to work, and B) How many shifts they can work.

So for example, Person 1 might say they can work shift 2 and 3, and would only like to work 1 of those. Person 2 might say they can work shift 1,2, or 3, and would like to work 2 shifts.

People working multiple shifts must work in consecutive ones (i.e. a person can not work shift 1 and 3).

How can I come up with a schedule from this information that maximizes the number of people working per shift?

Answer 1

This isn't really an answer, but it won't fit in a comment.

Unless you have some other goals, it seems like the problem is trivial.

1. If a person has only one schedule he's willing to work, give him that schedule.
2. If he's willing to work on more than one shift but wants to work only one shift, give him the earliest shift he's willing to work.
3. If he wants to work two shifts, but is willing to work any of the three shifts, put him on the first two shifts.

Now, this satisfies all the criteria you've enunciated, but I can't help feeling that it wouldn't be a satisfactory solution, since it favors the earlier shifts over the later shifts. If there are other criteria that you need to satisfy, please put them into the body of the question.

So far, the problem sounds like it can be formulated as a linear programming problem with $0-1$ variables. Suppose there are $n$ employees. We have $3n$ variables $x_{ij} \text{ where } 1\le i \le n, 1 \le j \le 3,$ all taking values in $\{0,1\}.$ The interpretation is that $x_{ij}=1$ if employee $i$ is assigned to shift $j,$ and $0$ otherwise.

Now, you want to maximize the sum of all the $x_{ij}$ subject to certain conditions. For example, if employee $i$ is willing to work shift $1$ or $3$, but not shift $2$, that would be represented as $x_{i1}+x_{i3}=1.$ If employee $i$ wants to work two shifts, and is willing to work on any shift, we have two conditions: $x_{i1}+x_{i2}+x_{i3}=2,$ and $x_{i1}+x_{i3}=1.$

If it weren't for the requirement that no one work shifts $1$ and $3,$ it seems to me that this could be modeled as an instance of network flow, with minimum and maximum capacities on the edges. That would probably be more efficient to solve than a linear programming problem. I don't see how to accommodate the rule, though.

This is sort of an operations research problem. I looked, but there isn't a Stack Exchange site for operations research. You might have good luck on the Computer Science site, though, because network flow is an important problem in computing.