2
$\begingroup$

I'm starting to learn operations research and trying to get my head around this problem that I have.

Problem statement: Find the minimum number of equipment needed to run a service schedule.

There are a set of machine types that need service during different times of the day for a period of 14 months (datetime data for each day of this period). Each machine requires a certain amount of different types of equipment for a set amount of time for the service.

Here's an example of what I mean: Machine MC001 requires 2 multimeters for a time period of 5 minutes from 18:35 pm to 18:55 pm on 30/09/2023 and it takes 2 minutes to move it from one service station to the next so ideally we would need a total of 2 Multimeters: From 18:35 to 18:40 for MC001 then we can add two minutes (18:42) for the equipment to move to MC002 Machine and then it can be used at MC002 from anywhere between 18:42 to 19:00

I want to formulate the problem in terms of decision variables, objective function, and constraints to get the minimum number of equipment that would be required for the whole service schedule period.enter image description here

Improve this question
$\endgroup$
11
  • $\begingroup$ I'm unclear on how exactly the equipment counts change. What are you deciding? The sequence of the machine moving from one station to the next? $\endgroup$
    – Reinderien
    Commented May 23, 2023 at 14:13
  • 1
    $\begingroup$ I am not sure if its indeed optimization/OR problem. Because such problems will require decision variables (continuous, integer, binary) with bounds. Constraints will also be bounds mostly ($ \le , \ge, \lt, \gt$). If all are relations with equal sign then perhaps best would be to use some heuristic or shopfloor planning s/w or even MS Project. $\endgroup$
    – Sutanu Majumdar
    Commented May 23, 2023 at 14:57
  • $\begingroup$ @Reinderien The equipment count changes based on the machine type. Each machine needs a specified number of equipment example Machine:MC001 will always need 2 "Multimeters" and 1 "work glove". There is no sequence of the machine moving from one station to the next rather the equipment would be moved from one machine to another, for example, there is a standard time of 2minute to move "Multimeter" from the MC001 machine to another machine. $\endgroup$
    – Asheesh
    Commented May 23, 2023 at 21:25
  • $\begingroup$ Thanks for the advice @Sutanu. What would be the problem if decision variables are with bounds? If we have to go through the OR approach can you give me an example of how the decision variables, objective function and constraints would look like? Don't have to be very brief just a basic understanding would help. thanks $\endgroup$
    – Asheesh
    Commented May 23, 2023 at 21:41
  • $\begingroup$ I still don't understand what you're deciding. What do you want the optimizer to tell you? $\endgroup$
    – Reinderien
    Commented May 23, 2023 at 22:02

1 Answer 1

Reset to default
1
$\begingroup$

Add decision variables for:

  • The actual start time of machine service within each window, continuous
  • The actual start time of machine service for a given piece of equipment, continuous
  • The actual duration of machine service for a given piece of equipment, continuous
  • Binary assignment variables: for each piece of equipment, is it assigned to a given machine service window?
  • The maximum value of the assignment variable per piece of equipment group, i.e. "is this piece of equipment used"; continuous

Constraints:

  • If assigned, the start time and duration of the equipment service must be equal to the start time and duration of the machine
  • The 'used' variable must be at least the value of each 'assigned' variable
  • Each machine must have a fixed value for the amount of assigned equipment
  • The difference between the stop time of the equipment service and the start time of the next equipment service must be at least 0, or at least the travel time if assigned
from datetime import datetime, timedelta

import pandas as pd
import pulp

df = pd.DataFrame(
    index=pd.Index(name='MachineName', data=('MC001', 'MC002')),
    data={
        'ServiceTimeStart': [datetime(2023, 9, 30, 18, 35), datetime(2023, 9, 30, 18, 37)],
        # 'ServiceTimeEnd':   [datetime(2023, 9, 30, 18, 40), datetime(2023, 9, 30, 18, 45)],  # would require all 4
        'ServiceTimeEnd':   [datetime(2023, 9, 30, 18, 55), datetime(2023, 9, 30, 19,  0)],
        'EquipName':        ['Multimeter', 'Multimeter'],
        'EquipServiceTime': [timedelta(minutes=5), timedelta(minutes=7)],
        'EquipRequired':    [2, 2],
        'EquipMoveTime':    [timedelta(minutes=2), timedelta(minutes=2)],
    },
)

first_time = df.ServiceTimeStart.min()
last_time = df.ServiceTimeEnd.max()
one_minute = timedelta(minutes=1)
max_time = (last_time - first_time)/one_minute
max_dur = df.EquipServiceTime.max()/one_minute

'''
one piece of equipment moves from machine to machine, with a fixed move time between them.
machines have fixed windows of time in which they can receive maintenance.
equipment maintenance time is given to be smaller than or equal to machine maintenance window time.

we assume that EquipServiceTime indicates the time for one equipment type and simultaneous use of
all instances of that piece of equipment at the same time.
'''

prob = pulp.LpProblem(name='machine_maintenance', sense=pulp.LpMinimize)

# in the worst case, every machine needs a dedicated equipment set;
# i.e. the amount of equipment is at most the sum of all EquipRequired
max_equip_required = df.groupby('EquipName').EquipRequired.sum()
equip_idx = max_equip_required.apply(range).explode()
equipment = pd.DataFrame({
    'EquipIdx': equip_idx,
    'EquipID': equip_idx.index + '_' + equip_idx.astype(str),
})


def make_machine_vars(row: pd.Series) -> pd.Series:
    # per machine and equipment type, we need to decide when - within
    # the maintenance window - the maintenance actually happens
    startoff = pulp.LpVariable(
        name=f'startoff_{row.name}_{row.EquipName}',
        cat=pulp.LpContinuous,
        lowBound=(
            row.ServiceTimeStart - first_time
        )/one_minute,
        upBound=(
            row.ServiceTimeEnd - first_time - row.EquipServiceTime
        )/one_minute,
    )
    return pd.Series(index=['StartOff'], data=[startoff])


df = pd.concat((df, df.apply(make_machine_vars, axis=1)), axis=1)


def make_combos(row: pd.Series):
    suffix = f'_{row.MachineName}_{row.EquipID}'

    # is this equipment assigned to this machine service?
    assign = pulp.LpVariable(name='assign' + suffix, cat=pulp.LpBinary)

    # the start and duration time for this equipment to service this machine
    startoff = pulp.LpVariable(
        name='startoff' + suffix, cat=pulp.LpContinuous,
        lowBound=0,
        upBound=max_time)
    duration = pulp.LpVariable(
        name='duration' + suffix, cat=pulp.LpContinuous,
        lowBound=0,
        upBound=max_dur)

    # if assigned, then the equipment start offset and duration must equal that of the machine
    start_error = startoff - row.StartOff
    dur_error = duration - row.EquipServiceTime/one_minute
    start_tol = 2*max_time*(1 - assign)
    dur_tol = 2*max_dur*(1 - assign)

    prob.addConstraint(name='startlo' + suffix, constraint=start_error <= start_tol)
    prob.addConstraint(name='starthi' + suffix, constraint=-start_error <= start_tol)
    prob.addConstraint(name='durlo' + suffix, constraint=dur_error <= dur_tol)
    prob.addConstraint(name='durhi' + suffix, constraint=-dur_error <= dur_tol)

    return pd.Series(
        index=['Assign', 'EquipStartOff', 'EquipDur'],
        data=[assign, startoff, duration])


# per machine and equipment instance
combos = pd.merge(
    left=df.reset_index(), right=equipment,
    left_on='EquipName', right_on='EquipName')
combos = pd.concat(
    (combos, combos.apply(make_combos, axis=1)),
    axis=1,
).set_index(['MachineName', 'EquipName', 'EquipIdx'])


def make_used(group: pd.DataFrame) -> pd.Series:
    # for each equipment instance: is it used at least once?
    used = pulp.LpVariable(
        name=f'used_{group.name}',
        cat=pulp.LpContinuous,
        lowBound=0,
    )

    # if any assign = 1, then used = 1
    for (machine_name, equip_name, equip_idx), row in group.iterrows():
        prob.addConstraint(
            name=f'usedmax_{machine_name}_{equip_name}_{equip_idx}',
            constraint=used >= row.Assign,
        )

    return pd.Series(index=['Used'], data=[used])


# the objective is to minimize the amount of used equipment
equipment['Used'] = (
    combos.groupby('EquipID')
    .apply(make_used)
    .set_index(equipment.index)
    .Used
)
prob.objective = equipment.Used.sum()

# for each machine service period, it has an enforced amount of equipment used
for (machine_name, equip_name), group in combos.groupby(level=['MachineName', 'EquipName']):
    prob.addConstraint(
        name=f'nequip_{machine_name}_{equip_name}',
        constraint=group.Assign.sum() == group.iloc[0,:].EquipRequired,
    )

# For every equipment instance,
for equip_id, equip_group in combos.groupby('EquipID'):
    # For every pair of chronologically consecutive machine service periods,
    machine_groups = tuple(equip_group.groupby(level='MachineName'))
    for (machine0_name, machine0), (machine1_name, machine1) in zip(
        machine_groups[:-1],
        machine_groups[1:],
    ):
        machine0 = machine0.iloc[0, :]
        machine1 = machine1.iloc[0, :]
        suffix = f'_{machine0_name}_{machine1_name}_{equip_id}'

        # the new start must be after the old stop, plus the move time if assigned
        slack = machine1.EquipStartOff - (machine0.EquipStartOff + machine0.EquipDur)
        min_pause = machine0.EquipMoveTime/one_minute * machine0.Assign
        prob.addConstraint(name='chrono' + suffix, constraint=slack >= min_pause)

print(prob)
prob.solve()

assert prob.status == pulp.LpStatusOptimal

pd.set_option('display.max_columns', 500)
pd.set_option('display.width', 1000)
print(f'{prob.objective.value()} pieces of equipment used')
print()

equipment['Used'] = equipment.Used.apply(pulp.LpVariable.value)
print(equipment)
print()

df['StartOff'] = first_time + df.StartOff.apply(pulp.LpVariable.value)*one_minute
print(df)
print()

combos[['StartOff', 'Assign', 'EquipStartOff', 'EquipDur']] = combos[[
    'StartOff', 'Assign', 'EquipStartOff', 'EquipDur',
]].applymap(pulp.LpVariable.value)
combos.EquipStartOff = first_time + combos.EquipStartOff*one_minute
combos.EquipDur *= one_minute
print(combos[['Assign', 'EquipStartOff', 'EquipDur']])
print()

This run is shown for the more difficult version where all four multimeters needs to be used:

machine_maintenance:
MINIMIZE
1*used_Multimeter_0 + 1*used_Multimeter_1 + 1*used_Multimeter_2 + 1*used_Multimeter_3 + 0
SUBJECT TO
startlo_MC001_Multimeter_0: 20 assign_MC001_Multimeter_0
 - startoff_MC001_Multimeter + startoff_MC001_Multimeter_0 <= 20

starthi_MC001_Multimeter_0: 20 assign_MC001_Multimeter_0
 + startoff_MC001_Multimeter - startoff_MC001_Multimeter_0 <= 20

durlo_MC001_Multimeter_0: 14 assign_MC001_Multimeter_0
 + duration_MC001_Multimeter_0 <= 19

durhi_MC001_Multimeter_0: 14 assign_MC001_Multimeter_0
 - duration_MC001_Multimeter_0 <= 9

...

usedmax_MC001_Multimeter_0: - assign_MC001_Multimeter_0 + used_Multimeter_0
 >= 0

usedmax_MC002_Multimeter_0: - assign_MC002_Multimeter_0 + used_Multimeter_0
 >= 0

...

nequip_MC001_Multimeter: assign_MC001_Multimeter_0 + assign_MC001_Multimeter_1
 + assign_MC001_Multimeter_2 + assign_MC001_Multimeter_3 = 2

nequip_MC002_Multimeter: assign_MC002_Multimeter_0 + assign_MC002_Multimeter_1
 + assign_MC002_Multimeter_2 + assign_MC002_Multimeter_3 = 2

chrono_MC001_MC002_Multimeter_0: - 2 assign_MC001_Multimeter_0
 - duration_MC001_Multimeter_0 - startoff_MC001_Multimeter_0
 + startoff_MC002_Multimeter_0 >= 0

chrono_MC001_MC002_Multimeter_1: - 2 assign_MC001_Multimeter_1
 - duration_MC001_Multimeter_1 - startoff_MC001_Multimeter_1
 + startoff_MC002_Multimeter_1 >= 0

...

VARIABLES
0 <= assign_MC001_Multimeter_0 <= 1 Integer
0 <= assign_MC001_Multimeter_1 <= 1 Integer
0 <= assign_MC001_Multimeter_2 <= 1 Integer
0 <= assign_MC001_Multimeter_3 <= 1 Integer
0 <= assign_MC002_Multimeter_0 <= 1 Integer
0 <= assign_MC002_Multimeter_1 <= 1 Integer
0 <= assign_MC002_Multimeter_2 <= 1 Integer
0 <= assign_MC002_Multimeter_3 <= 1 Integer
duration_MC001_Multimeter_0 <= 7 Continuous
duration_MC001_Multimeter_1 <= 7 Continuous
duration_MC001_Multimeter_2 <= 7 Continuous
duration_MC001_Multimeter_3 <= 7 Continuous
duration_MC002_Multimeter_0 <= 7 Continuous
duration_MC002_Multimeter_1 <= 7 Continuous
duration_MC002_Multimeter_2 <= 7 Continuous
duration_MC002_Multimeter_3 <= 7 Continuous
startoff_MC001_Multimeter = 0 Continuous
startoff_MC001_Multimeter_0 <= 10 Continuous
startoff_MC001_Multimeter_1 <= 10 Continuous
startoff_MC001_Multimeter_2 <= 10 Continuous
startoff_MC001_Multimeter_3 <= 10 Continuous
2 <= startoff_MC002_Multimeter <= 3 Continuous
startoff_MC002_Multimeter_0 <= 10 Continuous
startoff_MC002_Multimeter_1 <= 10 Continuous
startoff_MC002_Multimeter_2 <= 10 Continuous
startoff_MC002_Multimeter_3 <= 10 Continuous
used_Multimeter_0 Continuous
used_Multimeter_1 Continuous
used_Multimeter_2 Continuous
used_Multimeter_3 Continuous

Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

At line 2 NAME          MODEL
At line 3 ROWS
At line 51 COLUMNS
At line 192 RHS
At line 239 BOUNDS
At line 267 ENDATA
Problem MODEL has 46 rows, 30 columns and 120 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Continuous objective value is 2 - 0.00 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 8 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 8 strengthened rows, 0 substitutions
Cgl0004I processed model has 30 rows, 21 columns (8 integer (8 of which binary)) and 91 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 8 integers unsatisfied sum - 3.60216
Cbc0038I Pass   1: suminf.    2.49432 (7) obj. 2.75284 iterations 5
Cbc0038I Pass   2: suminf.    1.61364 (4) obj. 3.19318 iterations 8
Cbc0038I Pass   3: suminf.    0.00000 (0) obj. 4 iterations 2
Cbc0038I Solution found of 4
Cbc0038I Relaxing continuous gives 4
Cbc0038I Before mini branch and bound, 0 integers at bound fixed and 1 continuous
Cbc0038I Full problem 30 rows 21 columns, reduced to 30 rows 20 columns
Cbc0038I Mini branch and bound did not improve solution (0.03 seconds)
Cbc0038I Round again with cutoff of 2.90009
Cbc0038I Pass   4: suminf.    2.49432 (7) obj. 2.75284 iterations 0
...

Result - Optimal solution found

Objective value:                4.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.05
Time (Wallclock seconds):       0.05

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.06   (Wallclock seconds):       0.06

4.0 pieces of equipment used

           EquipIdx       EquipID  Used
EquipName                              
Multimeter        0  Multimeter_0   1.0
Multimeter        1  Multimeter_1   1.0
Multimeter        2  Multimeter_2   1.0
Multimeter        3  Multimeter_3   1.0

               ServiceTimeStart      ServiceTimeEnd   EquipName EquipServiceTime  EquipRequired   EquipMoveTime            StartOff
MachineName                                                                                                                        
MC001       2023-09-30 18:35:00 2023-09-30 18:40:00  Multimeter  0 days 00:05:00              2 0 days 00:02:00 2023-09-30 18:35:00
MC002       2023-09-30 18:37:00 2023-09-30 18:45:00  Multimeter  0 days 00:07:00              2 0 days 00:02:00 2023-09-30 18:37:00

                                 Assign       EquipStartOff        EquipDur
MachineName EquipName  EquipIdx                                            
MC001       Multimeter 0            1.0 2023-09-30 18:35:00 0 days 00:05:00
                       1            0.0 2023-09-30 18:35:00 0 days 00:00:00
                       2            0.0 2023-09-30 18:35:00 0 days 00:00:00
                       3            1.0 2023-09-30 18:35:00 0 days 00:05:00
MC002       Multimeter 0            0.0 2023-09-30 18:45:00 0 days 00:00:00
                       1            1.0 2023-09-30 18:37:00 0 days 00:07:00
                       2            1.0 2023-09-30 18:37:00 0 days 00:07:00
                       3            0.0 2023-09-30 18:45:00 0 days 00:00:00

You ask:

explain the code underneath the comment # if assigned, then the equipment start offset and duration must equal that of the machine.

This model has an offset and duration within the service window of the machine, and then a model and offset for every single equipment instance that might be assigned to that machine. If it is assigned, then the machine variables need to equal the equipment variables. This equality is enforced conditionally using a big M constraint.

I can't make out why we need to double the max_time: 2max_time(1 - assign) if there is no offset?

It's not if there's no offset; it's if there's no assignment. We double the maximum time to calculate a "big M": a coefficient sufficiently large enough that it can be guaranteed never smaller than the times with which it's compared.

how the logic for start_error = startoff - row.StartOff works?

In this context, startoff is the equipment-specific start time variable and row.StartOff is the machine start time variable. This defines the difference between the two. If the equipment is assigned, that difference is forced to 0; otherwise it's left unconstrained.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Much thanks for the answer @Reinderien, I'm going through the code that you have share (lot to learn and understand). can you please explain the code underneath the comment "# if assigned, then the equipment start offset and duration must equal that of the machine". I can't make out why we need to double the max_time: 2*max_time*(1 - assign) if there is no offset? Also how the logic for start_error = startoff - row.StartOff works? $\endgroup$
    – Asheesh
    Commented May 30, 2023 at 10:56
  • $\begingroup$ @Asheesh see answers in edit $\endgroup$
    – Reinderien
    Commented May 30, 2023 at 12:17
  • $\begingroup$ Thanks for you explaination @Reinderien, it makes sense now. I was wondering if there is a way to not hard code the machines mc001, mc002 in the for loop under the comment # For every equipment instance. And can we loop the code for each day of the schedule (14 months worth of data) to get the required equipments each day of the schedule? $\endgroup$
    – Asheesh
    Commented Jun 1, 2023 at 0:27
  • $\begingroup$ there is a way to not hard code the machines mc001, mc002 in the for loop under the comment # For every equipment instance - they aren't hard-coded; read it more carefully. That will loop through all machines, where 0 is the previous machine and 1 is the current machine. $\endgroup$
    – Reinderien
    Commented Jun 1, 2023 at 0:56
  • $\begingroup$ can we loop the code for each day of the schedule (14 months worth of data) to get the required equipments each day of the schedule? - yes; but that's somewhat over-extending this question and you should file a new one, marking this answer accepted if you believe that it answers your question. $\endgroup$
    – Reinderien
    Commented Jun 1, 2023 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.