Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Annals of Computer Science and Information Systems

2 Grigoreva Natalia

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

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.

Multiprocessor Scheduling Problem with Release and Delivery Times

Grigoreva Natalia

Annals of Computer Science and Information Systems

2020

Vol. 21

263--269

The multiprocessor scheduling problem is defined as follows: tasks have to be executed on several parallel identical processors. For each task we know release time, processing time and delivery time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. Preemption on processors is not allowed. The objective is to minimize the time, by which all tasks are delivered. Scheduling tasks among parallel processors is a NP-hard problem in the strong sense. The best known approximation algorithm is Jackson's algorithm, which generates the list schedule by giving priority to the ready job with the largest delivery time. This algorithm generates no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor is kept idle at a time when it could begin processing a task. The paper proposes the approximation inserted idle time algorithm for the multiprocessor scheduling. It is proved that deviation of this algorithm from the optimum is smaller then twice the largest processing time. To illustrate the efficiency of our approach we compared two algorithms on randomly generated sets of jobs.