Semi-online scheduling on two uniform parallel machines with initial lookahead

¹ Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, P.R. China
² School of Economics and Management, Tongji University, Shanghai 200092, P.R. China

^* Corresponding author: mingliu@tongji.edu.cn

Received: 18 November 2022
Accepted: 11 February 2024

Abstract

This work studies the problem of semi-online scheduling on two uniform parallel machines with speeds 1 and s (≥2), respectively. We introduce a novel concept of initial lookahead in which any deterministic online algorithm has the full knowledge of the first k jobs at the beginning, while the remaining jobs are released one-by-one in the online over-list mode. The objective of the considered problem is to minimize the makespan. We focus on the case where the first k jobs are of a total processing time not less than (s + 1)Δ where Δ is the largest job length, and it is assumed that s is an integer. We prove a lower bound of (s²+s+1)/(s²+s) , and propose a deterministic semi-online algorithm with competitive ratio of (s+1)²/s²+s+1. The ratio is at most 9/7 and much less than that of 1.618 for the corresponding case without initial lookahead (Cho and Sahni, SIAM J. Comput. 9 (1980) 91–103). Our results demonstrate that a finite ability of initial lookahead can greatly improve the competitiveness of online algorithms.