Qijia Liu, Jinjiang Yuan

Published:

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