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

Research paper by **Qijia Liu, Jinjiang Yuan**

Indexed on: **08 Aug '16**Published on: **01 Aug '16**Published in: **Journal of Combinatorial Optimization**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Abstract
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}\)
.AbstractIn 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}\)
.n
\(J_{j}\)
\(J_{j}\)
\(r_{j}\)
\(r_{j}\)
\(p_{j}\)
\(p_{j}\)
\(q_{j}\)
\(q_{j}\)
\(C_{\max } = \max _{1 \le j \le n} C_{j}\)
\(C_{\max } = \max _{1 \le j \le n} C_{j}\)
\(L_{\max } = \max _{1 \le j \le n} L_{j}\)
\(L_{\max } = \max _{1 \le j \le n} L_{j}\)
\(L_{j} = C_{j} + q_{j}\)
\(L_{j} = C_{j} + q_{j}\)
\(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)
\(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)
\(\rho \)
\(\rho \)
\( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\)
\( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\)