Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 International Journal of Applied Mathematics and Computer Science

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work

Xiao Man, Liu Xiaoqiao, Li Weidong, Chen Xin, Sterna Malgorzata, Blazewicz Jacek

International Journal of Applied Mathematics and Computer Science

2024

Vol. 34, no. 2

253--261

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.

Exact approaches to late work scheduling on unrelated machines

Liu Xinbo, Wang Wen, Chen Xin, Sterna Malgorzata, Blazewicz Jacek

International Journal of Applied Mathematics and Computer Science

2023

Vol. 33, no. 2

285--295

We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a dynamic programming algorithm. The time efficiencies of all three approaches are evaluated through computational experiments.