W zależności od ilości danych do przetworzenia generowanie pliku może się wydłużyć.

Jeśli generowanie trwa zbyt długo można ograniczyć dane np. zmniejszając zakres lat.

Artykuł

Pobierz BibTeX

Tytuł

Online early work scheduling on parallel machines

Autorzy

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

Dyscyplina naukowa (Ustawa 2.0)

[2.3] Informatyka techniczna i telekomunikacja

Rok publikacji

2024

Opublikowano w

European Journal of Operational Research

Rocznik: 2024 | Tom: vol. 315 | Numer: no. 3

Typ artykułu

artykuł naukowy

Język publikacji

angielski

Słowa kluczowe
EN
  • Combinatorial optimization
  • Parallel-machine scheduling
  • Early work
  • Online algorithm
  • Competitive ratio
Streszczenie

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.

Data udostępnienia online

09.01.2024

Strony (od-do)

855 - 862

DOI

10.1016/j.ejor.2024.01.009

URL

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

Punktacja Ministerstwa / czasopismo

140

Impact Factor

6 [Lista 2023]

Ta strona używa plików Cookies, w celu zapamiętania uwierzytelnionej sesji użytkownika. Aby dowiedzieć się więcej przeczytaj o plikach Cookies i Polityce Prywatności.