Online machine minimization with lookahead

摘要: This paper studies the online machine minimization problem, where jobs have real release times, uniform processing times and a common deadline. We investigate how lookahead ability improves performance of algorithms. Two models are studied, that is, additive multiplicative lookahead. At any time t, algorithm knows all to be released before $$t+L$$ (or $$\beta \cdot t$$ ) in multiplicative) model. propose $$\frac{e}{\alpha (e-1)+1}$$ -competitive with lookahead, $$\alpha = \frac{L}{T} \le 1$$ T is deadline jobs. For we provide an competitive ratio $$\frac{\beta e}{(\beta -1) e +1}$$ , \ge 1$$ . Lower bounds also provided for both two models, which show our algorithms optimal extreme cases, 0$$ 1$$ ) \rightarrow \infty $$ ), remain small gap cases between. Particularly, 1$$ ), e, corresponds problem without 1, offline version (with full information).