Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

In this paper, we consider the following single machine online tradeoff scheduling problem. A set of n independent jobs arrive online over time. Each job (J_{j}) has a release date (r_{j}), a processing time (p_{j}) and a delivery time (q_{j}). The characteristics of a job are unknown until it arrives. The goal is to find a schedule that minimizes the makespan (C_{max } = max _{1 le j le n} C_{j}) and the maximum lateness (L_{max } = max _{1 le j le n} L_{j}), where (L_{j} = C_{j} + q_{j}). For the problem, we present a nondominated (( rho , 1 + displaystyle frac{1}{rho } ))-competitive online algorithm for each (rho ) with ( 1 le rho le displaystyle frac{sqrt{5} + 1}{2}).