On-Line Scheduling of Unit Time Jobs with Rejection on Uniform Machines

The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is . The research is supported by the National Natural Science Foundation of China under Grant No. 10671108.