CAPACITATED 2-PARALLEL MACHINES SCHEDULING TO MINIMIZE SUM OF JOB COMPLETION TIMES

In this paper we study the n-job two-parallel machines scheduling problem with the objective of minimizing the sum of job completion times. However, instead of allowing both machines to be continuously available as is often assumed in the literature, we will only allow one of the machines to be available for a specified period of time after which it can no longer process any job. We will first prove that the problem is NP-complete and then provide a pseudo-polynomial dynamic programming algorithm to solve the problem. We will also propose a heuristic that has a worst case error bound of 50%. Other possible extensions to the problem will also be discussed.