Semi-Online Scheduling on Two Identical Parallel Machines with Initial-Lookahead Information
Abstract
This work investigates a new semi-online scheduling problem with lookahead. We focus on job scheduling on two identical parallel machines, where deterministic online algorithms only know the information of kk initial jobs (i.e., the initial-lookahead information), while the following jobs still arrive one-by-one in an over-list fashion. We consider makespan minimization as the objective. The study aims at revealing the value of knowing kk initial jobs, which are used to improve the competitive performance of those online algorithms without such initial-lookahead information. We provide the following findings: (1) For the scenario where the kk initial jobs are all the largest jobs with length ΔΔ, we prove that the classical LIST algorithm is optimal with competitive ratio (k+3)/(k+2)(k+3)/(k+2); (2) For the scenario where the total length of these k (>1)k (>1) jobs is at least ΔΔ, we show that any online algorithm has a competitive ratio at least 3/2, implying that the initial-lookahead knowledge is powerless since there exists a 3/2-competitive online algorithm without such information; (3) For the scenario where the total length of these k (>α)k (>α) jobs is at least αΔαΔ (α≥2α≥2), we propose an online algorithm, named as LPT-LIST, with competitive ratio of (α+2)/(α+1)(α+2)/(α+1), implying that the initial-lookahead information indeed helps to improve the competitiveness of those online algorithms lacking such information.
