51. Semi-Online Scheduling on Two Identical Parallel Machines with Initial-Lookahead Information.
- Author
-
Zheng, Feifeng, Chen, Yuhong, Liu, Ming, and Xu, Yinfeng
- Subjects
ONLINE algorithms ,DETERMINISTIC algorithms ,SCHEDULING ,PRODUCTION scheduling ,MACHINERY - 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 k 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 k 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 k 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) ; (2) For the scenario where the total length of these 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 (> α) jobs is at least α Δ (α ≥ 2), we propose an online algorithm, named as LPT-LIST, with competitive ratio of (α + 2) / (α + 1) , implying that the initial-lookahead information indeed helps to improve the competitiveness of those online algorithms lacking such information. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF