Online Preemptive Hierarchical Scheduling on Two Uniform Machines with Rejection

摘要

This paper studies the online hierarchical scheduling problem on two uniform machines with rejection. Two uniform machines M-1, M-2 run at the speeds of s is an element of (0, +infinity), 1 separately; and they are provided with different capabilities. Each machine has a certain GOS level 1 or 2 and every job is also associated with a hierarchy 1 or 2. The job can only be assigned to the machine whose GOS level does not exceed the job's hierarchy. Preemption is permitted but idle is not introduced. Jobs come one by one over list. When a job arrives, it can be accepted and scheduled on some machine or rejected by paying its penalty. The objective is to minimize the sum of makespan yielded by accepted jobs and total penalties of all rejected jobs. For this problem, we propose a family of several online algorithms according to the range of s and the related lower bound is also obtained. These algorithms achieve optimal competitive ratio when s is an element of (0, 1) boolean OR [1.618, +infinity), but have a small gap between upper bound and lower bound in interval [1, 1.618).