ONLINE AND SEMI-ONLINE SCHEDULING ON CAPACITATED TWO-PARALLEL MACHINES

In this paper, we investigate the capacitated two-parallel machines scheduling problem, where one machine is only available for a special period of time after which it can no longer process any job while the other machine is continuously available. Our objective is to minimize the completion time of the machine which is continuously available. The offline version of the problem is equivalent to the minimization version of the Subset-Sum problem. We first show the lower bound of the online version is infinite. We also consider the semi-online version with known the total job processing time in advance, for which both lower bound and semi-online algorithms are given.