Algorithmic analysis demonstrates an improved competitive ratio and lower bound in single-machine online job scheduling with rejection, highlighting sharper performance limits for squared makespans.
This paper investigates an online scheduling problem with rejection on a single machine. A sequence of independent jobs arrives sequentially, and each must be either accepted or rejected upon arrival. The objective is to minimize the sum of the square of the number of accepted jobs and the total penalty of rejected jobs. We propose a new online algorithm with a competitive ratio of [Formula: see text] and improve the lower bound for the problem to [Formula: see text].
No takes yet. Share an insight, caveat, or question.
Chen et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: