2
$\begingroup$

I have a problem to do with machine maintenance scheduling which I have formulated as a MIP where I have a binary variable $x_{ijt}$ which is 1 if the maintenance job j is scheduled on the same machine i at time t. Multiple jobs can be scheduled on the machine at the same time. In each time step I have a revenue loss $r_{t}$. If maintenance is scheduled in a given timestep the machine is "offline" and therefore loses revenue. The objective is to minimise the revenue loss from scheduling all jobs across all machines. What I am struggling to do is to avoid double counting the revenue loss for two jobs happening at the same time on a given machine. My current objective function formulation is: $$\min \sum_{i}\sum_{j}\sum_{t}{r_t \cdot x_{ijt}}$$

In this formulation if two jobs are scheduled at the same time we will double count the revenue loss from the machine being offline. What I have tried is to take the sum of $x$s happening at a given machine in a given timestep, subtract one and multiply by the revenue loss and subtract this from the objective function. However, this doesn't work for time periods where there is no maintenance at all scheduled on a machine.

Is anyone able to provide some guidance on how to formulate the objective function or additional variables to avoid the double counting of revenue loss from scheduling multiple jobs on the same machine at the same time?

Some examples of scenarios are provided in the tables below.

Example 1 - no overlap between jobs on the same machine

In this case we can just sum the revenue losses for all jobs. So revenue loss for periods 1-2, 3-4 and 8-10.

t 1 2 3 4 5 6 7 8 9 10
$x_{00t}$ 1 1 0 0 0 0 0 0 0 0
$x_{01t}$ 0 0 1 1 0 0 0 0 0 0
$x_{02t}$ 0 0 0 0 0 0 0 1 1 1

Example 2 - overlap between jobs on the same machine

In this case we only need to sum the revenue losses from time periods 1-3

t 1 2 3 4 5 6 7 8 9 10
$x_{00t}$ 1 1 0 0 0 0 0 0 0 0
$x_{01t}$ 1 1 0 0 0 0 0 0 0 0
$x_{02t}$ 1 1 1 0 0 0 0 0 0 0
$\endgroup$

1 Answer 1

4
$\begingroup$

You want to minimize $\sum_i \sum_t r_t \max_j x_{ijt}$. To linearize this objective, introduce binary decision variable $y_{it}$ to represent $\max_j x_{ijt}$, impose constraints $x_{ijt} \le y_{it}$, and minimize $\sum_i \sum_t r_t y_{it}$.

$\endgroup$
1
  • $\begingroup$ I have just implemented this and it works great, you've even helped me reformulate a more complex problem to work in this way! $\endgroup$
    – Demitri
    Commented Jun 18 at 13:26

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.