Research output: Contribution to journal › Article › peer-review
Алгоритм составления расписания для одного процессора с гарантированной оценкой точности 3/2. / Григорьева, Наталья Сергеевна.
In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ, Vol. 17, No. 3, 2021, p. 240-253.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 86372435