Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations $OP = \{OP_1, OP_2, \ldots, OP_K\}$. Each operation $OP_i$ can server multiple jobs, but each job can only be served by one operation at each time unit. Now the question is to prove that finding a scheduling scheme that can result in the minimum sum of the finishing time of the $m$ jobs is NP-hard.

Here is an example to illustrate the above problem. Suppose there are 8 jobs $J= \{J_1, J_2, \ldots, J_8\}$, $2$ machines $M=\{M_1, M_2\}$ and 3 operations $OP = \{OP_1, OP_2, OP_3\}$. For each job, there are $J_1 = \{OP_1, OP_2\}$, $J_2 = \{OP_1\}$, $J_3 = \{OP_1\}$, $J_4 = \{OP_1, OP_3\}$, $J_5 = \{OP_2\}$, $J_6 = \{OP_2\}$, $J_7 = \{OP_2\}$ and $J_8 = \{OP_3\}$. Now we need to find a scheduling scheme of $OP = \{OP_1, OP_2, OP_3\}$ on the two processors to minimizing the finishing time of the 8 jobs.

For example, we can allocate $OP_2$ and $OP_3$ on the two processors at the first time unit, and then allocate $OP_1$ on any one of the two processors at the second time unit. Obviously, under this scheduling, all jobs can be satisfied, and the sum of the finishing time of the 8 jobs is $2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 = 12$.

As another choice, We can also allocate $OP_1$ and $OP_2$ on the two processors at the first time unit. Note here since each job can only be served by one operation at each time unit, $J_1$ can only be served by either $OP_1$ or $OP_2$ at the first time unit, and we need to allocate $OP_2$ (or $OP_1$) at the second time unit to finish $J_1$. Suppose here at the first time unit, $J_1$ is served by $OP_1$, then it means we need to allocate $OP_2$ and $OP_3$ on the two processors at the second time unit to satisfy all the jobs. Under this scheduling, the sum of the finishing time of the 8 jobs is $2 + 1 + 1 + 2 + 1 + 1 + 1 + 2 = 11$.

My question is how to prove the NP-hardness of the above problem. Any suggestions or comments will be highly appreciated.

Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations $OP = \{OP_1, OP_2, \ldots, OP_K\}$. Each operation $OP_i$ can server multiple jobs, but each job can only be served by one operation at each time unit. Now the question is to prove that finding a scheduling scheme that can result in the minimum sum of the finishing time of the $m$ jobs is NP-hard.

Here is an example to illustrate the above problem. Suppose there are 8 jobs $J= \{J_1, J_2, \ldots, J_8\}$, $2$ machines $M=\{M_1, M_2\}$ and 3 operations $OP = \{OP_1, OP_2, OP_3\}$. For each job, there are $J_1 = \{OP_1, OP_2\}$, $J_2 = \{OP_1\}$, $J_3 = \{OP_1\}$, $J_4 = \{OP_1, OP_3\}$, $J_5 = \{OP_2\}$, $J_6 = \{OP_2\}$, $J_7 = \{OP_2\}$ and $J_8 = \{OP_3\}$. Now we need to find a scheduling scheme of $OP = \{OP_1, OP_2, OP_3\}$ on the two processors to minimize the finishing time of the 8 jobs.

For example, we can allocate $OP_2$ and $OP_3$ on the two processors at the first time unit, and then allocate $OP_1$ on any one of the two processors at the second time unit. Obviously, under this scheduling, all jobs can be satisfied, and the sum of the finishing time of the 8 jobs is $2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 = 12$.

As another choice, We can also allocate $OP_1$ and $OP_2$ on the two processors at the first time unit. Note here since each job can only be served by one operation at each time unit, $J_1$ can only be served by either $OP_1$ or $OP_2$ at the first time unit, and we need to allocate $OP_2$ (or $OP_1$) at the second time unit to finish $J_1$. Suppose here at the first time unit, $J_1$ is served by $OP_1$, then it means we need to allocate $OP_2$ and $OP_3$ on the two processors at the second time unit to satisfy all the jobs. Under this scheduling, the sum of the finishing time of the 8 jobs is $2 + 1 + 1 + 2 + 1 + 1 + 1 + 2 = 11$.

My question is how to prove the NP-hardness of the above problem. Any suggestions or comments will be highly appreciated.