Help with a MILP formulation for service scheduling

Question

I'm trying to formulate a MILP for scheduling service jobs for multiple devices. Let's assume that each device $i$ has a life $\ell_i$ and that I have $n$ total service visits to allocate at times $\{M_1,\ldots,M_n\}$. Each device must be serviced. I would like to maximize the average time of service per device -- understanding that some devices will share a service (think 2 service visits for 5 devices).

So far, I have

Objective $$\max \sum_j \sum_i M_j x_{ij}\tag1$$

Constraints

• $\sum_j x_{ij} = 1$, $\forall i$ (every device is serviced once) (2)
• $\sum_i x_{ij} \geq 1$, $\forall j$ (every job services one or more devices) (3)
• $M_j x_{ij} \leq \ell_i$, $\forall i,j$ (each device has a service before the end of life) (4)

Variables

• $M_j \geq 0$ $\forall j$,

  • $x_{ij} \in \{0,1\}$ $\forall i,j$

I realize that $M_j x_{ij}$ is nonlinear. I can rearrange (4) to make it linear ($M_j \leq \ell_i (1+c(1-x_{ij})$ where $c$ is very large), but I'm still stuck with the nonlinear term in the objective.

Is there a way to restate the objective, so I can use a MILP solver? Or perhaps a better way to formulate the entire problem? I don't have a background in integer programming, so even suitable problem classes are a bit of a mystery to me.

Answer 1

There is a way to formulate the problem with everything linear. (You can decided if it is better.) Set a time horizon $T$ (could be the last end-of-life epoch among the devices). Let $x_{it}$ be 1 if device $i$ is serviced at time $t\in \lbrace 1,\dots, T\rbrace$, 0 if not. Let $y_t$ be 1 if there is a service visit at time $t$, 0 if not.

Consider the following model: \begin{align} \max&\quad\sum_{i}\sum_{t}tx_{it}\\ \textrm{s.t. }&\quad\sum_{t}x_{it}=1&\forall i\\ &\quad\sum_{t}tx_{it}\le\ell_{i}&\forall i\\ &\quad x_{it}\le y_{t}&\forall i,t\\ &\quad y_{t}\le\sum_{i}x_{it}&\forall t\\ &\quad \sum_{t}y_{t}=n. \end{align}

The objective maximizes the sum of the service dates. The first constraint ensures every device is serviced once. The second constraint requires each device be serviced before it dies. The third constraint ensures that devices are only serviced during visits, the fourth prevents idle visits, and the fifth forces exactly $n$ visits. (You might want to consider making the last constraint an inequality, in case not all $n$ visits are needed.) This assumes that there is no limit on how many devices can be serviced at any one time.