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

Research paper by Qijia Liu, Jinjiang Yuan

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

#### 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}$$