Depending on the amount of data to process, file generation may take longer.

If it takes too long to generate, you can limit the data by, for example, reducing the range of years.

Article

Download BibTeX

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)

[2.3] Information and communication technology

Year of publication

2024

Published in

European Journal of Operational Research

Journal year: 2024 | Journal volume: in press

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

DOI

10.1016/j.ejor.2024.01.009

URL

https://www.sciencedirect.com/science/article/abs/pii/S0377221724000092?via%3Dihub

Ministry points / journal

140

Impact Factor

6,4 [List 2022]

This website uses cookies to remember the authenticated session of the user. For more information, read about Cookies and Privacy Policy.