17
Aug

# Operations Research 03H: Linear Programming Staff Scheduling Problem

In this video, I’ll talk about how to formulate
a special type of LP problem called the staff scheduling problem. Let’s see an example. A company requires different numbers of employees
on different days of the week. This table shows the numbers of needed employees
for every day. Wednesday is the busiest day and the company
needs 20 employees on duty. Sunday is the least busy day and the company
needs 5 employees on duty. Each employee must work five consecutive days
and then receive two days off. For example, an employee who works on Monday
through Friday must be off on Saturday and Sunday. An employee who works on Saturday through
Wednesday must be off on Thursday and Friday. Formulate a LP problem to minimize the number
of employees who must be hired. Before we talk about the correct problem formulation,
let’s look at this wrong problem formulation. In this formulation, we define xi as the number
of employees working on day i, i is from 1 to 7. With this variable definition, the problem
formulation is listed here. The constraints are very straightforward. x1 is greater than or equal to 10, x2 is greater
than or equal to 12, and so on. Although unrealistic, we assume xi can take
fraction numbers so it will be a LP problem. The objective function is the sum of x1 through
x7. What’s wrong with this formulation? We are actually double counting many employees. For example, if an employee works from Monday
to Friday, he or she is counted in x1, x2, x3, x4, and x5. So he or she is counted five times in the
objective function. The reason for this wrong formulation is that
the decision variables are inappropriate. Now let’s change the variable definition to
this. xi is the number of employees beginning to
work on day i, i is from 1 to 7. We still assume that xi can take fraction
numbers so it will be a LP problem. With this variable definition, now let’s look
at the schedule. From Monday to Sunday, the needed numbers
of employees are listed here. The schedules are shown in this table. x1 represents the number of employees starting
to work on Monday. They will work from Monday to Friday. x2 represents the number of employees starting
to work on Tuesday. They will work from Tuesday to Saturday. And so on. So, the total number of employees needed is
just the sum of x1 through x7. We are not double counting any employee in
this case. The total number of employees working on Monday
will be x1+x4+x5+x6+x7 and it should be greater than or equal to 10. The total number of employees working on Tuesday
will be x1+x2+x5+x6+x7 and it should be greater than or equal to 12. And so on. With this definition, the objective function
is the sum of x1 through x7. The problem formulation is listed here. This is the correct problem formulation. Okay, that is how to formulate the staff scheduling
LP problem. Thanks for watching.

• Jingzheng Song says:

谢谢老师 讲的挺好

• Alejandro Avelar says:

Thanks man!

• icem4n says:

why is employee x6 and x7 starting work on the same day? I thought they should be all starting on different days?