Online scheduling on a single machine with grouped processing times (Q1723520)

Summary: We consider the online scheduling problem on a single machine with the assumption that all jobs have their processing times in \([p,(1 + \alpha) p]\), where \(p > 0\) and \(\alpha = (\sqrt{5} - 1) / 2\). All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs should be first processed on a single machine and then delivered by a vehicle to some customer. When the capacity of the vehicle is infinite, we provide an online algorithm with the best competitive ratio of \((\sqrt{5} + 1) / 2\). When the capacity of the vehicle is finite, that is, the vehicle can deliver at most \(c\) jobs at a time, we provide another best possible online algorithm with the competitive ratio of \((\sqrt{5} + 1) / 2\).