Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Scheduling Algorithms for Single Machine Problem with Release and Delivery Times. / Григорьева, Наталья Сергеевна.
Recent Advances in Computational Optimization - Results of the Workshop on Computational Optimization WCO 2021: Results of the Workshop on Computational Optimization WCO 2021. ред. / Stefka Fidanova. 2022. стр. 61-77 (Studies in Computational Intelligence; Том 1044).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Scheduling Algorithms for Single Machine Problem with Release and Delivery Times
AU - Григорьева, Наталья Сергеевна
PY - 2022
Y1 - 2022
N2 - The problem of minimizing the maximum delivery times while scheduling jobs on the single processor is a classical combinatorial optimization problem. Each job has a release time, processing time and a delivery time. The objective is to minimize the time, by which all jobs are delivered. This problem is denoted by 1 | r j, q j| C max, has many applications, and it is NP-hard in strong sense. The problem is useful in solving flowshop and jobshop scheduling problems. The goal of this paper is to propose a new 3/2—approximation algorithm, which runs in O(nlog n) times for scheduling problem 1 | r j, q j| C max. We present an example which shows that the bound of 3/2 is tight. To compare the effectiveness of proposed algorithms we tested random generated problems of up to 5000 jobs.
AB - The problem of minimizing the maximum delivery times while scheduling jobs on the single processor is a classical combinatorial optimization problem. Each job has a release time, processing time and a delivery time. The objective is to minimize the time, by which all jobs are delivered. This problem is denoted by 1 | r j, q j| C max, has many applications, and it is NP-hard in strong sense. The problem is useful in solving flowshop and jobshop scheduling problems. The goal of this paper is to propose a new 3/2—approximation algorithm, which runs in O(nlog n) times for scheduling problem 1 | r j, q j| C max. We present an example which shows that the bound of 3/2 is tight. To compare the effectiveness of proposed algorithms we tested random generated problems of up to 5000 jobs.
KW - Approximation algorithm
KW - Release and delivery times
KW - Single-machine scheduling problem
KW - Worst-case performance ratio
UR - http://www.scopus.com/inward/record.url?scp=85138830939&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/dcd22fca-1068-3114-bd75-cb860c333422/
U2 - 10.1007/978-3-031-06839-3_4
DO - 10.1007/978-3-031-06839-3_4
M3 - Conference contribution
SN - 9783031068386
T3 - Studies in Computational Intelligence
SP - 61
EP - 77
BT - Recent Advances in Computational Optimization - Results of the Workshop on Computational Optimization WCO 2021
A2 - Fidanova, Stefka
T2 - 14th Workshop on Computational Optimization
Y2 - 2 September 2021 through 5 September 2021
ER -
ID: 100243513