Practical data science and optimization: scheduling problem


In this post we consider several examples of optimal scheduling (see [1]).

Problem 1.

Your business provide support services to other businesses, 24 hours per day. According to demands from your clients you need to have the following number of employees to satisfy the demand,

t1

The objective is to schedule employees for 8 hour shifts so as to minimize the total number of employees to meet requirements on each shift, which minimize costs for your business.

Solution

Let x1 is a number of employees who start at 8:00 and work till 16:00, x2 is a number of employees who start at 12:00 and work till 20:00, x3 is a number of employees who start at 16:00 and work till 24:00, x4 is a number of employees who start at 20:00 and work till 4:00, x5 is a number of employees who start at 24:00 and work till 8:00, x6 is a number of employees who start at 4:00 and work till 12:00. All these variables must be positive integers or zeroes. We want to minimize z=x1+x2+x3+x4+x5+x6 and the following conditions must be satisfied:

x6+x1>=7

x1+x2>=6

x2+x3>=8

x3+x4>=12

x4+x5>=5

x5+x6>=4

x1-x6 all non-negative integers.

 

Create a file problem1.py and copy the text below into the file.

from scipy.optimize import linprog

obj=[1,1,1,1,1,1] #sum x[i] i=1,6 minimize

lhs_ineq=[[-1,0,0,0,0,-1],

[-1,-1,0,0,0,0],

[0,-1,-1,0,0,0],

[0,0,-1,-1,0,0],

[0,0,0,-1,-1,0],

[0,0,0,0,-1,-1]]

rhs_ineq=[-7,-6,-8,-12,-5,-4]

integ=[3,3,3,3,3,3] #all x[i] integer or zero

opt=linprog(c=obj,A_ub=lhs_ineq,b_ub=rhs_ineq,integrality=integ,method="highs")

print(opt)

 

Run it with this command: python3 problem1.py

You will see the result.

p1

The optimal solution is: x1=6, x2=0, x3=10, x4=2, x5=3, x6=1, z=22.

 

Problem 2

Peter’s restaurant is open 24 hours a day. Servers report for duty at 3am, 7am, 11am, 3pm, 7pm, 11pm and work 8-hours shifts. The minimum numbers of servers needed during the six periods are shown in the table below.

t2

Peter needs to determine how many servers should report for work at the start of each time period in order to minimize the staff required for the restaurant's operation.

Solution

Let x1 is the number of servers that begin work at 3am and work 8 hours till 11am, x2 is the number of servers that begin work at 7am and work 8 hours till 3pm, x3 is the number of servers that begin work at 11am and work 8 hours till 7pm, x4 is the number of servers that begin work at 3pm and work 8 hours till 11pm, x5 is the number of servers that begin work at 7pm and work 8 hours till 3am, x6 is the number of servers that begin work at 11pm and work 8 hours till 7am.

From the table above, we have the following constraints:

x6+x1>=1 for period 1

x1+x2>=3 for period 2

x2+x3>=7 for period 3

x3+x4>=3 for period 4

x4+x5>=5 for period 5

x5+x6>=2 for period 6

x1-x6 all non-negative integers.

The objective is to minimize the total number of servers needed to meet all shifts requirements z=x1+x2+x3+x4+x5+x6.

Create a file problem2.py and copy the text below into the file.

from scipy.optimize import linprog

obj=[1,1,1,1,1,1] #sum x[i] i=1,6 minimize

lhs_ineq=[[-1,0,0,0,0,-1],

[-1,-1,0,0,0,0],

[0,-1,-1,0,0,0],

[0,0,-1,-1,0,0],

[0,0,0,-1,-1,0],

[0,0,0,0,-1,-1]]

rhs_ineq=[-1,-3,-7,-3,-5,-2]

integ=[3,3,3,3,3,3] #all x[i] integer or zero

opt=linprog(c=obj,A_ub=lhs_ineq,b_ub=rhs_ineq,integrality=integ,method="highs")

print(opt)

 

Run it with this command: python3 problem2.py

You will see the result.

p2

The optimal solution is: x1=1, x2=2, x3=5, x4=0, x5=5, x6=0, z=13.

 

Problem 3

The emergency unit of a local hospital needs the optimal schedule for its nurses. The hospital schedules nurses for 16 hours shifts. The beginning times for the shifts are 6am, 2pm, and 10pm. A nurse beginning a shift works the next 16 hours. During normal and week day operations, the number of nurses needed varies depending on the time of the day. The hospital stuffing guidelines require the following minimum number of nurses on duty.

t3

The hospital wants to minimize the total number of nurses to meet all shifts and requirements.

Solution

Let x1 is the number of nurses that begin work at 6am and work till 10pm, x2 is the number of nurses that begin work at 2pm and work till 6am, x3 is the number of nurses that begin work at 10am and work till 2pm. From the table above we have the following constrains:

x1+x3>=6

x1+x2>=5

x2+x3>=3

x1-x3 all non-negative integers.

The objective is to minimize the total number of nurses z=x1+x2+x3 and satisfy all the required constrains.

Create a file problem3.py and copy the text below into the file.

from scipy.optimize import linprog

obj=[1,1,1] #sum x[i] i=1,3 minimize

lhs_ineq=[[-1,0,-1],

[-1,-1,0],

[0,-1,-1,]]

rhs_ineq=[-6,-5,-3]

integ=[3,3,3,3,3,3] #all x[i] integer or zero

opt=linprog(c=obj,A_ub=lhs_ineq,b_ub=rhs_ineq,integrality=integ,method="highs")

print(opt)

 

Run it with this command: python3 problem3.py

You will see the result.

p3

The optimal solution is: x1=4, x2=1, x3=2, z=7.

 

Problem 4

Julia is responsible for scheduling security guards for 8-hour shifts in several shopping malls. The beginning times for the shifts and the minimum numbers of security guards required are shown in the table below.

t4

Julia wants to minimize the total number of security guards to meet all shift requirements.

Solution

Let x1 is the number of security guards that begin work at 8am and work till 4pm, x2 is the number of security guards that begin work at Noon and work till 8pm, x3 is the number of security guards that begin work at 4pm and work till Midnight, x4 is the number of security guards that begin work at 8pm and work till 4am, x5 is the number of security guards that begin work at Midnight and work till 8am, x6 is the number of security guards that begin work at 4am and work till Noon.

From the table above, we have the following constraints:

x6+x1>=5

x1+x2>=6

x2+x3>=10

x3+x4>=7

x4+x5>=4

x5+x6>=6

x1-x6 all non-negative integers.

Objective is to minimize the total number of security guards z=x1+x2+x3+x4+x5+x6.

Create a file problem4.py and copy the text below into the file.

from scipy.optimize import linprog

obj=[1,1,1,1,1,1] #sum x[i] i=1,6 minimize

lhs_ineq=[[-1,0,0,0,0,-1],

[-1,-1,0,0,0,0],

[0,-1,-1,0,0,0],

[0,0,-1,-1,0,0],

[0,0,0,-1,-1,0],

[0,0,0,0,-1,-1]]

rhs_ineq=[-5,-6,-10,-7,-4,-6]

integ=[3,3,3,3,3,3] #all x[i] integer or zero

opt=linprog(c=obj,A_ub=lhs_ineq,b_ub=rhs_ineq,integrality=integ,method="highs")

print(opt)

 

Run it with this command: python3 problem4.py

You will see the result.

p4

The optimal solution is: x1=3, x2=3, x3=7, x4=0, x5=4, x6=2, z=19.

Scheduling problems arise in many situations where we need to assign people or resources in optimal way, subject to some restrictions or constraints.

 

References:

[1] Application of Linear Programming in Scheduling Problem

https://www.banglajol.info/index.php/DUJS/article/download/54526/38311

 

 

How do you rate this article?

25


I_g_o_r
I_g_o_r

I am curious about science, technologies and their applications to solving real problems.


Practical data science & optimization in examples
Practical data science & optimization in examples

This blog gives readers practical examples of data science and optimization problems and their solutions using python scripts. These scripts can be used to solve real problems in business and life.

Send a $0.01 microtip in crypto to the author, and earn yourself as you read!

20% to author / 80% to me.
We pay the tips from our rewards pool.