pythonlinear-programmingpulp

Python Pulp Query - allocate task within timerange to achieve objective to minimize number of resource


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


Solution

  • 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:

    Create the following constraints:

    The 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