Linear programming conditional constraint

Question

There are 22 drivers. Each driver has to work min of 7.6 hrs and can work max of 10 hrs. Each driver cost and productivity is different.

if some driver works overtime (more than 7.6 hrs), for first 2 hrs, we need to pay 1.5 times. For remaining 0.4 hrs, we need to pay 2 times.

195 hrs of work has to be completed by 22 drivers. We need to schedule in such a way that cost can be minimized.

Driver,Cost,Productivity
A,70,0.8
B,22,0.8
C,24,0.8
D,26,0.8
E,28,0.8
F,30,0.8
G,32,0.8
H,34,0.8
I,36,0.8
J,38,0.8
K,40,0.8
L,42,0.9
M,44,0.9
N,46,0.9
O,48,0.9
P,50,0.9
Q,52,0.9
R,54,0.9
S,56,0.9
T,58,0.9
U,60,0.9
V,62,0.5

Decision Variables:

X1,X2 ........X22 represents the total number of hours allocated to each driver

Objective Function:

Min Z = 20*X1 +22*X2......62*X22

Constraints:

X1>=7.6,X2>=7.6....X22>=7.6

X1<=10,X2<=10....X22<=10

X1+X2.....+X22 <= 195

I have tried following python program so far.

import pulp
import pandas as pd


def main():
    model = pulp.LpProblem("Cost minimising scheduling problem", pulp.LpMinimize)

    totalHours = 192
    minHourEachDriver = 7.6
    maxHourEachDriver = 10

    # importing data from CSV

    drivers = pd.DataFrame.from_csv('csv/drivers.csv', index_col=['Driver', 'Cost', 'Productivity'])

    # Decision Variables
    drv = pulp.LpVariable.dicts("driverName", indexs=((i) for i, j, k in drivers.index), lowBound=0,
                                cat='Continuous')

    # Objective
    model += pulp.lpSum([j * (1 / k) * drv[i] for i, j, k in drivers.index]), "Cost"

    # Constraints

    # total no of hours work to be done
    model += pulp.lpSum([drv[i] for i, j, k in drivers.index]) == totalHours

    for i, j, k in drivers.index:
        # minimum hours driver has to work
        model += drv[i] >= minHourEachDriver
        # Maximum hour driver can work
        model += drv[i] <= maxHourEachDriver

    model.solve()

    # model status
    print(pulp.LpStatus[model.status])

    # Total Cost
    print(pulp.value(model.objective))

    # No of hrs allocated to each driver

    for i, j, k in drivers.index:
        var_value = drv[i].varValue
        # print(var_value)
        print("The number hours for driver {0} are {1}".format(i, var_value))


if __name__ == '__main__':
    main()

But, I am not able to figure out, how do we put following constraint.

if some driver work overtime (more than 7.6 hrs), for first 2 hrs, we need to pay 1.5 times. For remaining 0.4 hrs, we need to pay 2 times.

kozo kozo · Accepted Answer · 2019-03-19T14:37:48

If for each driver is mandatory to work 7.6h, there is no need to put it in the conditions. It is just static time (cost) that can be subtracted from total hours (costs) because it always happen:

195 - (NumDrivers * 7.6) = is the remaining time that need to be flexibly distributed between drivers as their overtimes to reach the 195 hours (when total hours > NumDrivers*7,6).

I would represent each driver with two variables (one for time working at 1.5 rate and second working time at double rate) and make following LP:

Xij = represents hours allocated to i-driver in j-working mode (let's say j=1 for 1,5 and j=2 for 2)

Based on the provided input file:

Min Z = 70*1,5*X11 + 70*2*X12 + 22*1,5*X21 + 22*2*X22 + ... 62*1,5*X221 + 62*2*X222

Constraints:

X11+X12+X21+X22+...X221+X222 = 27,8 (195 - (22*7,6))

X11+X12 <= 3,4 X21+X22 <= 3,4 ... X221+X222 <= 3,4

X11<=2 X21<=2 ... X221<=2

For the completeness there should be also set of conditions representing that each driver can start with j mode (2*) only after completing 2 hours at 1.5* but in this case objective function should make it automatically.

Linear programming conditional constraint

1 Answers