Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time

In this paper we introduce the concept of online tradeoff scheduling to minimize two objective functions f1 and f2 simultaneously. An online algorithm A is called (ρ1,ρ2)-competitive for minimizing f1 and f2 if A is ρ1-competitive for minimizing f1 and ρ2-competitive for minimizing f2. A (ρ1,ρ2)-competitive online algorithm A is called nondominated if there is no other (ρ1′,ρ2′)-competitive online algorithm A′ such that (ρ1′,ρ2′)≤(ρ1,ρ2) and either ρ1′<ρ1 or ρ2′<ρ2.For the online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time, we present a nondominated (1+α,1+1/α)-competitive online algorithm for each α with 0<α≤1.