Title
Online early work scheduling on parallel machines
Authors
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska, Poznań, Polska | [ P ] employee
Scientific discipline (Law 2.0)
Year of publication
2024
Published in
Article type
scientific article
Publication language
english
Keywords
EN
- Combinatorial optimization
- Parallel-machine scheduling
- Early work
- Online algorithm
- Competitive ratio
Abstract
EN We consider non-preemptive online parallel-machine scheduling with a common due date to maximize the total early work of all the jobs, i.e., the total processing time of the jobs (or parts) completed before the common due date. For the general case of 𝑚 machines, we provide a parameter lower bound with respect to 𝑚. For the online algorithm, we first show that the tight competitive ratio of the classical list scheduling (LS) algorithm is 4/3. We then improve the upper bound on the competitive ratio for the previous algorithm, EFF𝑚, to 1.2956. Additionally, we present a formula to compute the upper bound on the competitive ratio for any given 𝑚. For the case of three machines, we improve the lower bound to 1.1878 and propose an improved online algorithm with a tight competitive ratio of 1.2483.
Date of online publication
09.01.2024
Pages (from - to)
855 - 862
Ministry points / journal
140
Impact Factor
6
System created by Poznań University of Technology
and Poznan Supercomputing and Networking Center
Log in through eKonto to add to SIS