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)
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
| 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
The following answer describes the theoretical optimisation approach, data processing steps, and output; but does not include verbatim code because I'm not compelled to spoon-feed the OP.
Use Pandas. It's the only practical way to manage this dataset, especially due to the non-trivial date manipulation necessary. Replace your long column names with short (but still descriptive) ones.
The date format 22W211 is cursed - it's not useful in any processing context. As soon as you can, throw this away and replace it with a version parsed by format %yW%U%w. This can be done in one step in Pandas via pd.to_datetime.
Hour counts are also not helpful here. Convert to day counts by dividing by 8. Treat those counts as continuous and monotonic on a datetime index from Pandas date_range() using frequency B. Pay careful attention to the fact that the work-day dimension in integers referenced from some arbitrary epoch is not the same as calendar days, and if you attempt to perform math on the dates as calendar days it won't be valid.
Your resources being a series of comma-delimited strings is also useless in any processing context. Use Pandas str.split() followed by explode to convert to a long-form frame to represent requirement-resource combinations.
Create the following variables in PuLP:
any_used per resource: binary, whether that resource was used at allasn_req_res per requirement and resource: binary, whether that requirement-resource pair was assignedres_ok for every resource, first requirement and second requirement: binary, whether the first and second requirements are clear from schedule conflict. Skip rows for which the first and second requirement are the same.start per requirement: continuous, the start of the contiguous schedule block for that requirement. This is in units of work days as referenced from some arbitrary epoch, and is bounded based on the Available range columns from the dataset.Create the following constraints:
lpSum(asn_req_res) == 1: requirements must have exactly one resource assignedres_ok: let M = 2*(latest work day - earliest work day); let slack = 2 - first res_ok - second res_ok; then constrain
(first res_ok - slack - 1)*M <= dist_x, where dist_x is the signed difference between the second start and the first end(second res_ok - slack - 1)*M <= dist_y where dist_y is the signed difference between the first start and the second endfirst res_ok + second res_ok == 1: either the first order must have no conflict, or the second order must have no conflict; i.e. for this resource and requirement pair, the requirement schedule segments must not conflict if both of the requirements are assigned to this resourceM*any_used >= n_uses, where M is the number of resources and n_uses is the sum of asn_req_res for this resourceThe objective is to minimize the sum of any_used. For your current input data, this executes in 0.03 seconds and produces the following output:
res_scheduling:
MINIMIZE
1*any_used_RES1 + 1*any_used_RES2 + 1*any_used_RES3 + 1*any_used_RES4 + 0
SUBJECT TO
req_unique_1: asn_req_res_(1,_'RES1') + asn_req_res_(1,_'RES2')
+ asn_req_res_(1,_'RES3') + asn_req_res_(1,_'RES4') = 1
req_unique_2: asn_req_res_(2,_'RES1') + asn_req_res_(2,_'RES2')
+ asn_req_res_(2,_'RES3') + asn_req_res_(2,_'RES4') = 1
req_unique_3: asn_req_res_(3,_'RES1') + asn_req_res_(3,_'RES2')
+ asn_req_res_(3,_'RES3') + asn_req_res_(3,_'RES4') = 1
...
res_ok_x_RES1_req1_2: 600 asn_req_res_(1,_'RES1')
+ 600 asn_req_res_(2,_'RES1') + 600 res_ok_('RES1',_1,_2) + start_1 - start_2
<= 1785
res_ok_y_RES1_req1_2: 600 asn_req_res_(1,_'RES1')
+ 600 asn_req_res_(2,_'RES1') + 600 res_ok_('RES1',_2,_1) - start_1 + start_2
<= 1795
either_ok_RES1_req1_2: res_ok_('RES1',_1,_2) + res_ok_('RES1',_2,_1) = 1
res_ok_x_RES1_req1_3: 600 asn_req_res_(1,_'RES1')
+ 600 asn_req_res_(3,_'RES1') + 600 res_ok_('RES1',_1,_3) + start_1 - start_3
<= 1785
res_ok_y_RES1_req1_3: 600 asn_req_res_(1,_'RES1')
+ 600 asn_req_res_(3,_'RES1') + 600 res_ok_('RES1',_3,_1) - start_1 + start_3
<= 1790
either_ok_RES1_req1_3: res_ok_('RES1',_1,_3) + res_ok_('RES1',_3,_1) = 1
...
any_used_RES1: 4 any_used_RES1 - asn_req_res_(1,_'RES1')
- asn_req_res_(2,_'RES1') - asn_req_res_(3,_'RES1') - asn_req_res_(4,_'RES1')
>= 0
any_used_RES2: 4 any_used_RES2 - asn_req_res_(1,_'RES2')
- asn_req_res_(10,_'RES2') - asn_req_res_(2,_'RES2')
- asn_req_res_(3,_'RES2') - asn_req_res_(4,_'RES2') - asn_req_res_(5,_'RES2')
- asn_req_res_(6,_'RES2') - asn_req_res_(7,_'RES2') - asn_req_res_(8,_'RES2')
- asn_req_res_(9,_'RES2') >= 0
any_used_RES3: 4 any_used_RES3 - asn_req_res_(1,_'RES3')
- asn_req_res_(2,_'RES3') - asn_req_res_(3,_'RES3') - asn_req_res_(4,_'RES3')
- asn_req_res_(5,_'RES3') - asn_req_res_(6,_'RES3') - asn_req_res_(7,_'RES3')
- asn_req_res_(8,_'RES3') - asn_req_res_(9,_'RES3') >= 0
any_used_RES4: 4 any_used_RES4 - asn_req_res_(1,_'RES4')
- asn_req_res_(2,_'RES4') - asn_req_res_(3,_'RES4') - asn_req_res_(4,_'RES4')
- asn_req_res_(5,_'RES4') - asn_req_res_(6,_'RES4') - asn_req_res_(7,_'RES4')
- asn_req_res_(8,_'RES4') - asn_req_res_(9,_'RES4') >= 0
...
VARIABLES
0 <= any_used_RES1 <= 1 Integer
0 <= any_used_RES2 <= 1 Integer
0 <= any_used_RES3 <= 1 Integer
0 <= any_used_RES4 <= 1 Integer
0 <= asn_req_res_(1,_'RES1') <= 1 Integer
0 <= asn_req_res_(1,_'RES2') <= 1 Integer
0 <= asn_req_res_(1,_'RES3') <= 1 Integer
0 <= asn_req_res_(1,_'RES4') <= 1 Integer
...
0 <= res_ok_('RES1',_1,_2) <= 1 Integer
0 <= res_ok_('RES1',_1,_3) <= 1 Integer
0 <= res_ok_('RES1',_1,_4) <= 1 Integer
0 <= res_ok_('RES1',_2,_1) <= 1 Integer
0 <= res_ok_('RES1',_2,_3) <= 1 Integer
0 <= res_ok_('RES1',_2,_4) <= 1 Integer
0 <= res_ok_('RES1',_3,_1) <= 1 Integer
0 <= res_ok_('RES1',_3,_2) <= 1 Integer
0 <= res_ok_('RES1',_3,_4) <= 1 Integer
0 <= res_ok_('RES1',_4,_1) <= 1 Integer
0 <= res_ok_('RES1',_4,_2) <= 1 Integer
0 <= res_ok_('RES1',_4,_3) <= 1 Integer
...
250 <= start_1 <= 285 Continuous
250 <= start_10 <= 260 Continuous
250 <= start_2 <= 255 Continuous
250 <= start_3 <= 290 Continuous
start_4 <= 14 Continuous
start_5 <= 12 Continuous
start_6 <= 13 Continuous
start_7 = 270 Continuous
250 <= start_8 <= 270 Continuous
250 <= start_9 <= 255 Continuous
...
Welcome to the CBC MILP Solver
At line 2 NAME MODEL
At line 3 ROWS
At line 388 COLUMNS
At line 2501 RHS
At line 2885 BOUNDS
At line 3184 ENDATA
Problem MODEL has 383 rows, 292 columns and 1544 elements
...
Result - Optimal solution found
Objective value: 3.00000000
Enumerated nodes: 0
Total iterations: 73
Time (CPU seconds): 0.03
Time (Wallclock seconds): 0.03
The solution looks like
hours work_days start_code end_code earliest latest_excl start end_excl resources earliest_work_day latest_work_day_excl resource
requirement
1 120 15.0 22W211 22W305 2022-05-23 2022-07-30 2022-07-11 2022-08-01 [RES1, RES2, RES3, RES4] 250 300 RES2
2 40 5.0 22W211 22W225 2022-05-23 2022-06-04 2022-05-23 2022-05-30 [RES1, RES2, RES3, RES4] 250 260 RES2
3 80 10.0 22W211 22W305 2022-05-23 2022-07-30 2022-07-18 2022-08-01 [RES1, RES2, RES3, RES4] 250 300 RES4
4 8 1.0 21W231 21W255 2021-06-07 2021-06-26 2021-06-07 2021-06-08 [RES1, RES2, RES3, RES4] 0 15 RES3
5 24 3.0 21W231 21W255 2021-06-07 2021-06-26 2021-06-23 2021-06-28 [RES2, RES3, RES4] 0 15 RES4
6 16 2.0 21W231 21W255 2021-06-07 2021-06-26 2021-06-07 2021-06-09 [RES2, RES3, RES4] 0 15 RES4
7 120 15.0 22W251 22W275 2022-06-20 2022-07-09 2022-06-20 2022-07-11 [RES2, RES3, RES4] 270 285 RES3
8 240 30.0 22W211 22W305 2022-05-23 2022-07-30 2022-05-23 2022-07-04 [RES2, RES3, RES4] 250 300 RES4
9 40 5.0 22W211 22W225 2022-05-23 2022-06-04 2022-05-23 2022-05-30 [RES2, RES3, RES4] 250 260 RES3
10 120 15.0 22W211 22W255 2022-05-23 2022-06-25 2022-05-30 2022-06-20 [RES2] 250 275 RES2
resource start end_excl work_days
requirement
2 RES2 2022-05-23 2022-05-30 5.0
10 RES2 2022-05-30 2022-06-20 15.0
1 RES2 2022-07-11 2022-08-01 15.0
4 RES3 2021-06-07 2021-06-08 1.0
9 RES3 2022-05-23 2022-05-30 5.0
7 RES3 2022-06-20 2022-07-11 15.0
6 RES4 2021-06-07 2021-06-09 2.0
5 RES4 2021-06-23 2021-06-28 3.0
8 RES4 2022-05-23 2022-07-04 30.0
3 RES4 2022-07-18 2022-08-01 10.0