# 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.

谢谢老师 讲的挺好

Thanks man!

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

how should I go about the problem if the constraint is that the employees cannot work for three consecutive days?

Hi Guys, please comment and let me know what you think about this Operations Research Open Course. Your feedback is really appreciated. If you enjoy the video, please subscribe and share. All my replies here are only related to the content in my own videos. I am afraid I won't be able to answer other questions. Thanks for your understanding.