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}$$ J j has a release date $$r_{j}$$ r j , a processing time $$p_{j}$$ p j and a delivery time $$q_{j}$$ 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}$$ C max = max 1 ≤ j ≤ n C j and the maximum lateness $$L_{\max } = \max _{1 \le j \le n} L_{j}$$ L max = max 1 ≤ j ≤ n L j , where $$L_{j} = C_{j} + q_{j}$$ L j = C j + q j . For the problem, we present a nondominated $$( \rho , 1 + \displaystyle \frac{1}{\rho } )$$ ( ρ , 1 + 1 ρ ) -competitive online algorithm for each $$\rho $$ ρ with $$ 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}$$ 1 ≤ ρ ≤ 5 + 1 2 .