A Note on On-Line Scheduling of Unit Jobs with Rejection to Minimize the Squared Makespan

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].