Online scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost

• Scheduling to minimize total completion time plus total rejection cost.
• An agreeable condition extends the common job rejection penalty.
• We present a best possible online algorithm of competitive ratio 2.

We consider the single-machine online scheduling with job rejection to minimize the total completion time of the scheduled jobs plus the total rejection cost of the rejected jobs under an agreeable condition on the processing times and rejection penalties of the jobs. In the problem, a set of independent jobs arriving online over time has to be scheduled on the machine with the flexibility of rejecting some of the jobs, where preemption is not allowed and the information of each job JjJj, including its processing time pjpj, release date rjrj and rejection penalty ejej, is not known in advance. The agreeable condition means that, for every two jobs JiJi and JjJj, pi