Online scheduling with delivery time on a bounded parallel batch machine with limited restart (Q1666180)

Summary: We consider the online (over time) scheduling of equal length jobs on a bounded parallel batch machine with batch capacity \(b\) to minimize the time by which all jobs have been delivered with limited restart. Here, ``restart'' means that a running batch may be interrupted, losing all the work done on it, and jobs in the interrupted batch are then released and become independently unscheduled jobs, called restarted jobs. ``Limited restart'' means that a running batch which contains some restarted jobs cannot be restarted again. When \(b = 2\), we propose a best possible online algorithm \(H(b = 2)\) with a competitive ratio of \(1 + \alpha\), where \(\alpha\) is the positive solution of \(2 \alpha(1 + \alpha) = 1\). When \(b \geq 3\), we present a best possible online algorithm \(H(b \geq 3)\) with a competitive ratio of \(1 + \beta\), where \(\beta\) is the positive solution of \(\beta(1 + \beta)^2 = 1\).