[Python] Python Pulp Query - allocate task within timerange to achieve objective to minimize...

Objective


Minimize the number of resource to handle all requirements The input that we have is list of requirements which needs to be allocated to any one of the resource from list of resource that can be mapped. Each requirement needs to be allocated for duration as per no of hours requested and within the range of dates provided in request.

Challenge


The code that I shared below allocates resource from start date(Available range(start day)) in input, it doesn’t find out from given range of days(Available range(start day) Available range(end day)), which date is best to have as start date so that the total number of cars to be manufactured can be minimized.

For eg: In below sample input – req 1 can be allocated to any resource and for any 3 weeks from range provided. The number of weeks in request 1 is 3 weeks(120/40) which can be allocated from 22W211 to 22W235 or 22W221 to 22W245 or 22W231 to 22W255 or 22W241 to 22W265 etc

Sample input

Req ID Nr.hrs to allocate Available range(start day) Available range(end day) List of resource to which the requirement can be mapped
1 120 22W211 22W305 RES1, RES2, RES3, RES4
2 40 22W211 22W225 RES1, RES2, RES3, RES4
3 80 22W211 22W305 RES1, RES2, RES3, RES4
4 8 21W231 21W255 RES1, RES2, RES3, RES4
5 24 21W231 21W255 RES2, RES3, RES4
6 16 21W231 21W255 RES2, RES3, RES4
7 120 22W251 22W275 RES2, RES3, RES4
8 240 22W211 22W305 RES2, RES3, RES4
9 40 22W211 22W225 RES2, RES3, RES4
10 120 22W211 22W255 RES2

RES_LIST = unique set of resource that is mentioned in table we created copy of res list so that same res can be created multiple time. resource can be assumed as robots, we can have multiple copy of same robot if that can reduce the number of robots to be bought.

# Create a linear programming problem using pulp
prob = pulp.LpProblem("RES_Scheduling", pulp.LpMinimize)

# Binary variables to indicate if a res is used or not
RES_LIST = pulp.LpVariable.dicts('RES_LIST', res_list, cat='Binary')

# Binary variables to indicate if a copied res is used or not
RES_LIST_copied = pulp.LpVariable.dicts('RES_LIST_copied', [item for sublist in copied_res.values() for item in sublist],
cat='Binary')

# BInary variables to indicate assignment of res to requirement
ASSIGNMENT = pulp.LpVariable.dicts('ASSIGNMENT', (range(len(Requirements)), range(len(RES_LIST) + len(RES_LIST_copied))), cat='Binary')
# print(ASSIGNMENT)
# Objective function: Minimize the number of res used

prob += pulp.lpSum([RES_LIST[RES] for RES in RES_list]) + pulp.lpSum([RES_LIST_copied[RES] for RES in RES_LIST_copied])

# Constraint: Ensue each test need is assigned 1 RES or copied RES
for i, need in enumerate(Requirements):
prob += pulp.lpSum([ASSIGNMENT[j] for j, RES in enumerate(RES_List+ list(RES_LIST_copied)) if RES.split('-')[0] in need['RES']]) == 1
# Constraint: Ensure assignment variables are consistent with usage variables
for j, RES in enumerate(RES_List+ list(RES_LIST_copied)):
if RES.split('-')[0] in need['RESs']:
if '-' in RES: # If its a copied RES
prob += ASSIGNMENT[j] <= RES_LIST_copied[RES] # Ensure ASSIGNMENT[j] is only 1 if RES_LIST_copied[RES] is 1
else: # If its an original RES
prob += ASSIGNMENT[j] <= RES_LIST[RES] # Ensure ASSIGNMENT[j] is only 1 if RES_LIST[RES] is 1


# Constraint: Ensure resource are not overbooked on any day (no overlapping allowed)
for day in range(min([need['start_day'] for need in Requirements]),
max([need['end_day'] for need in Requirements]) + 1):
for j, RES in enumerate(RES_List+ list(RES_LIST_copied)):
prob += pulp.lpSum([ASSIGNMENT[j] for i, need in enumerate(Requirements) if
day >= need['start_day'] and day <= need['end_day']]) <= 1



result = prob.solve()

Continue reading...