Abstract:

We consider the online scheduling problem on two parallel machines with the Grade of Service (GoS) eligibility constraints. The jobs arrive over time, and the objective is to minimize the makespan. We develop a (1 + α)-competitive optimal algorithm, where α ≈ 0.555 is a solution of α3 − 2α2 − α + 1 = 0.

Key words: Scheduling ·, Parallel machine ·, Eligibility constraint ·, Online algorithm