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

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}\)