An instance of the multiple$-$machine interval scheduling $($MMIS$)$ problem specifies an integer $k,$ a set of machines $x,$ and a set of jobs $Y.$ Each job $y$ in $Y$ has an associated start time $s_y,$ finish time $f_y,$ and set of machines $x_y$subex. A schedule specifies a subset

$Y^{\text{'}}$ of the jobs, and a machine in $x_y$ on which to schedule each job $y$ in $Y^{\text{'}}.($The jobs in $\frac{Y}{\frac{?}{?}}{Y}^{\text{'}}$ are not scheduled.$)$ We define the size of such a schedule as $|Y^{\text{'}}|.$ A schedule is said to be feasible if $[s_y,f_y)[s_{y^{\text{'}}},f_{y^{\text{'}}})=\frac{O}{?}$ for all distinct jobs $y$ and $y^{\text{'}}$ scheduled

on the same machine. The MMIS problem asks whether there is a feasible schedule of size at least $k.$ Prove that the MMIS problem is NP$-$complete.

Hint: Reduce the maximum independent set $($IS$)$ problem to MMIS. In one solution, any given IS instance $(G,k^{**})$ where $G=(V,E)$ is transformed into an MMIS instance $(x,Y,k)$ where $x=V,|Y|=|E|+|V|,$ and $k=|E|+k^{**}.$