Алгоритм составления расписания для одного процессора с гарантированной оценкой точности 3/2

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

The problem of minimizing the maximum delivery times while scheduling tasks on a single processor is a classical combinatorial optimization problem. Each task ui must be processed without interruption for t(u(i)) time units on the machine, which can process at most one task at time. Each task ui has a release time r(u(i)), when the task is ready for processing, and a delivery time q(u(i)). Its delivery begins immediately after processing has been completed. The objective is to minimize the time, by which all jobs are delivered. In the Graham notation this problem is denoted by 1 vertical bar r(j), q(j)vertical bar C-max, it has many applications and it is NP-hard in a strong sense. The problem is useful in solving owshop and jobshop scheduling problems. The goal of this article is to propose a new 3/2-approximation algorithm, which runs in O(n log n) times for scheduling problem 1 vertical bar r(j), q(j)vertical bar C-max. An example is provided which shows that the bound of 3/2 is accurate. To compare the effectiveness of proposed algorithms, random generated problems of up to 5000 tasks were tested.

Язык оригиналарусский
Страницы (с-по)240-253
Число страниц14
Журнал ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ
Том17
Номер выпуска3
DOI
СостояниеОпубликовано - 2021

Предметные области Scopus

  • Математика (все)

Цитировать