Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: release time

Sortuj według:

Ogranicz wyniki do:

Worst-Case Analysis of an Approximation Algorithm for Single Machine Scheduling Problem

Grigoreva Natalia

Annals of Computer Science and Information Systems

2021

Vol. 25

221--225

—The problem of minimizing the maximum delivery times while scheduling jobs on the single processor is a classical combinatorial optimization problem. This problem is denoted by 1|rj,qj|Cmax has many applications, and it is NP-hard in strong sense. The goal of this paper is to propose a new 3/2approximation algorithm, which runs in O(n log n) time. We proved that the bound of 3/2 is tight. To check the efficiency of the algorithm we tested it on random generated problems of up to 5000 jobs.