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.