I formulated a MILP to model a multi-period multi-customer scheduling problem in PuLP. The aim is to schedule multiple batches of products to be produced in a week such that all the product batches are manufactured by minimizing total cost of labor. Each day has a regular shift and an over-time shift(which is more expensive to use due to the variable cost of labor).
I've used two variables both that are created as 'Integer' variables. However, I still get decimal and negative values in my problem solution. How is this possible? Please see my code below.
'''
Multi-Period Scheduling Problem
'''
from pulp import *
import itertools
Creating the parameters and data:
'''SETS'''
#list of batch_id's waiting for production
batch_ids = ['b1', 'b2', 'b3', 'b4', 'b5', 'b6']
#list of the days available in a week
days = ['mon', 'tue', 'wed', 'thu', 'fri']
#list of shifts in a day
shifts= ['rt', 'ot']
'''PARAMETERS'''
#batch quantity needed
batch_size= {
'b1': 45,
'b2': 60,
'b3': 120,
'b4': 80,
'b5': 230,
'b6': 40
}
#regular time and over time values
time_dict= {'rt': 450, 'ot': 300}
#dict to store minutes available per day per shift
mins_per_day= {d: {s: time_dict[s] for s in shifts} for d in days}
#cycle time in minutes per unit per batch
cycle_time = {
'b1': 45,
'b2': 30,
'b3': 10,
'b4': 80,
'b5': 13,
'b6': 35
}
'''minimum needed units per batch per day; as of now this is a fixed qty= 10, but we can create a separate
dict to store different qty per batch if needed and then use it in the dict comprehension here'''
min_qty= {d:{b: 5 for b in batch_ids} for d in days}
pay_by_shift= {'ot': 0.8625, 'rt': 0.575}
#cost per minute per shift per day:
pay_dict= {d: {s: pay_by_shift[s] for s in shifts} for d in days}
#indexes for batch and day combinations
shifts_ind = [(d,s) for d in days for s in shifts]
#indexes for the make variable:
make_ind= [(d,b) for d in days for b in batch_ids]
Defining the variables:
'''VARIABLES'''
#number of units of a batch scheduled for production per day per shift
make= LpVariable.dicts("Make Per Day",(days, batch_ids, shifts),0, None, cat= 'Integer')
#binary variable to decide wether OT is scheduled on a given day or not
y= LpVariable.dicts("Use Shift",(days, shifts), 0, 1, cat= 'Integer')
'''model formulation'''
#create model object with a minimize objective
prob= LpProblem("FlexLine Problem",LpMinimize)
Defining the Objective Function
#objective function
prob += lpSum([y[d][s] for d in days for s in shifts]) + \
lpSum([make[d][b][s]* cycle_time[b]* pay_dict[d][s] for d in days for b in batch_ids for s in shifts]), "Total labor cost per week"
Defining the constraints:
'''CONSTRAINTS'''
#demand constraint
for b in batch_ids:
prob += lpSum([make[d][b][s] for d in days for s in shifts]) == batch_size[b]
#time constraint
for (d,s) in shifts_ind:
prob += lpSum([make[d][b][s] * cycle_time[b] for b in batch_ids]) <= mins_per_day[d][s] * y[d][s]
#minimum per day constraint
for (d,b) in make_ind:
prob += lpSum([make[d][b][s] for s in shifts]) >= min_qty[d][b]
#linking constraint
for (d,s) in shifts_ind:
prob += lpSum([make[d][b][s] for b in batch_ids]) <= 100000 * y[d][s]
Solving the model:
prob.solve()
Out: -1
print ("Status:", LpStatus[prob.status])
Out: Status: Infeasible
Printing the variable values:
for v in prob.variables():
print (v.name, "=", v.varValue)
Out:Make_Per_Day_fri_b1_ot = 0.0
Make_Per_Day_fri_b1_rt = 5.0
Make_Per_Day_fri_b2_ot = 0.0
Make_Per_Day_fri_b2_rt = -5.5
Make_Per_Day_fri_b3_ot = 0.0
Make_Per_Day_fri_b3_rt = 5.0
Make_Per_Day_fri_b4_ot = 1.5625
Make_Per_Day_fri_b4_rt = 3.4375
Make_Per_Day_fri_b5_ot = 0.0
Make_Per_Day_fri_b5_rt = 5.0
Make_Per_Day_fri_b6_ot = 5.0
Make_Per_Day_fri_b6_rt = 0.0
Make_Per_Day_mon_b1_ot = 0.0
Make_Per_Day_mon_b1_rt = 5.0
Make_Per_Day_mon_b2_ot = 0.0
Make_Per_Day_mon_b2_rt = -5.5
Make_Per_Day_mon_b3_ot = 0.0
Make_Per_Day_mon_b3_rt = 5.0
Make_Per_Day_mon_b4_ot = 2.9375
Make_Per_Day_mon_b4_rt = 2.0625
Make_Per_Day_mon_b5_ot = 5.0
Make_Per_Day_mon_b5_rt = 0.0
Make_Per_Day_mon_b6_ot = 0.0
Make_Per_Day_mon_b6_rt = 5.0
Make_Per_Day_thu_b1_ot = 25.0
Make_Per_Day_thu_b1_rt = 0.0
Make_Per_Day_thu_b2_ot = 61.0
Make_Per_Day_thu_b2_rt = 0.0
Make_Per_Day_thu_b3_ot = 131.5
Make_Per_Day_thu_b3_rt = 0.0
Make_Per_Day_thu_b4_ot = 60.0
Make_Per_Day_thu_b4_rt = 0.0
Make_Per_Day_thu_b5_ot = 210.0
Make_Per_Day_thu_b5_rt = 0.0
Make_Per_Day_thu_b6_ot = 16.142857
Make_Per_Day_thu_b6_rt = 12.857143
Make_Per_Day_tue_b1_ot = 5.0
Make_Per_Day_tue_b1_rt = 0.0
Make_Per_Day_tue_b2_ot = 0.83333333
Make_Per_Day_tue_b2_rt = 4.1666667
Make_Per_Day_tue_b3_ot = 5.0
Make_Per_Day_tue_b3_rt = 0.0
Make_Per_Day_tue_b4_ot = 0.0
Make_Per_Day_tue_b4_rt = 5.0
Make_Per_Day_tue_b5_ot = 0.0
Make_Per_Day_tue_b5_rt = 5.0
Make_Per_Day_tue_b6_ot = 0.0
Make_Per_Day_tue_b6_rt = -4.0
Make_Per_Day_wed_b1_ot = 5.0
Make_Per_Day_wed_b1_rt = 0.0
Make_Per_Day_wed_b2_ot = 5.0
Make_Per_Day_wed_b2_rt = 0.0
Make_Per_Day_wed_b3_ot = -26.5
Make_Per_Day_wed_b3_rt = 0.0
Make_Per_Day_wed_b4_ot = 1.5625
Make_Per_Day_wed_b4_rt = 3.4375
Make_Per_Day_wed_b5_ot = 5.0
Make_Per_Day_wed_b5_rt = 0.0
Make_Per_Day_wed_b6_ot = 0.0
Make_Per_Day_wed_b6_rt = 5.0
Use_Shift_fri_ot = 1.0
Use_Shift_fri_rt = 1.0
Use_Shift_mon_ot = 1.0
Use_Shift_mon_rt = 1.0
Use_Shift_thu_ot = 41.216667
Use_Shift_thu_rt = 1.0
Use_Shift_tue_ot = 1.0
Use_Shift_tue_rt = 1.0
Use_Shift_wed_ot = 1.0
Use_Shift_wed_rt = 1.0
To reiterate, I am seeing negative values, decimals as well as binary variables showing up as more than 1. How is this happening?
