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. Start date and end date range format w 24w211 is 2024 week 21 and day 1(Monday)
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 |
def solve_group(res_pool, reqs): # Initialize the linear programming problem prob = LpProblem(f"Minimize_ress_Group_{res_pool}", LpMinimize)
# Step 2.1: Define variables
# Decision variable x_ijk = 1 if res i is assigned to request j starting at week k
x = {}
for res in res_pool:
for req in reqs:
for start_day in range(req['start_day'], req['end_day'] + 2 - req['hours_required'] // 8 - (1 if req['hours_required'] % 8 > 0 else 0) ):
x[res, req['req_id'], start_day] = LpVariable(f"x_{res}_{req['req_id']}_{start_day}", 0, 1, LpBinary)
# Step 2.2: Define binary variable for res usage
# Binary variable used_i = 1 if res i is used
used = {}
for res in res_pool:
used[res] = LpVariable(f"used_{res}", 0, 1, LpBinary)
# Step 3: Objective function - Minimize the number of ress used
prob += lpSum(used[res] for res in res_pool), "Minimize number of res"
# Step 4: Constraints
# Step 4.1: Every request must be fulfilled
for req in reqs:
prob += lpSum(x[res, req['req_id'], start_day]
for res in req['pnos']
for start_day in range(req['start_day'], req['end_day'] + 2 - req['hours_required'] // 8 - (1 if req['hours_required'] % 8 > 0 else 0))) == 1, f"Fulfill_req_{req['req_id']}"
# Step 4.2: Non-overlapping constraint - No res can be double-booked for overlapping periods
for res in res_pool:
for day in range(min(req['start_day'] for req in reqs), max(req['end_day'] for req in reqs)):
prob += lpSum(x[res, req['req_id'], start_day]
for req in reqs
for start_day in range(req['start_day'], req['end_day'] + 2 - req['hours_required'] // 8 - (1 if req['hours_required'] % 8 > 0 else 0) )
if start_day <= day < start_day + (req['hours_required'] // 8 + (1 if req['hours_required'] % 8 > 0 else 0) )) <= 1, f"No_double_booking_{res}_{day}"
# Step 4.3: Link res usage with assignment
for res in res_pool:
for req in reqs:
for start_day in range(req['start_day'], req['end_day'] + 2 - req['hours_required'] // 8 - (1 if req['hours_required'] % 8 > 0 else 0) ):
prob += used[res] >= x[res, req['req_id'], start_day], f"Link_usage_{res}_{req['req_id']}_{start_day}"
# Step 5: Solve the problem for this group
prob.solve()
# Return the result (the number of res used and their assignments)
return prob, used, x
Another example: Also if Consider the are 3 requirements, req 1 has need for 1 week with range of 24w20 and 24w22 and req 2, req 3 also has same requirement. In this case all three can be assigned to one resource, req1 can be mapped on 24w20 and req2 can be mapped to 24w21 and req2 can be mapped to 24w22. This way we minimised number of resource needed for handling all requirements
