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.


Download BibTeX


Online and Semi-online Scheduling on Two Hierarchical Machines with a Common Due Date to Maximize the Total Early Work


[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee

Scientific discipline (Law 2.0)

[2.3] Information and communication technology

Year of publication


Published in

International Journal of Applied Mathematics and Computer Science

Journal year: 2024 | Journal volume: vol. 34 | Journal number: no. 2

Article type

scientific article

Publication language


  • online and semi-online
  • early work
  • hierarchical scheduling
  • competitive ratio

EN In this study, we investigate several online and semi-online scheduling problems related to two hierarchical machines with a common due date to maximize the total early work. For the pure online case, we design an optimal online algorithm with a competitive ratio of √2. Additionally, for the cases when the largest processing time is known, we give optimal algorithms with a competitive ratio of 6/5 if the largest job is a lower-hierarchy one, and of √5 − 1 if the largest job is a higher-hierarchy one.

Pages (from - to)

253 - 261


License type

CC BY-NC-ND (attribution - noncommercial - no derivatives)

Open Access Mode

open journal

Open Access Text Version

final published version

Date of Open Access to the publication

at the time of publication

Ministry points / journal


Impact Factor

1,6 [List 2023]

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