TY - JOUR

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

AU - Григорьева, Наталья Сергеевна

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - single-machine scheduling problem

KW - realize and delivery times

KW - approximation algorithm

KW - guarantee approximation ratio

KW - Single-machine scheduling problem

KW - Guarantee approximation ratio

KW - Approximation algorithm

KW - Realize and delivery times

UR - https://www.mendeley.com/catalogue/79a5d656-73f5-3ebd-9a53-30bfe5339a49/

UR - http://www.scopus.com/inward/record.url?scp=85119067978&partnerID=8YFLogxK

U2 - 10.21638/11701/spbu10.2021.302

DO - 10.21638/11701/spbu10.2021.302

M3 - статья

VL - 17

SP - 240

EP - 253

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

SN - 1811-9905

IS - 3

ER -