Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. / Grigoreva, Natalia .
INFORMATION SYSTEMS ARCHITECTURE AND TECHNOLOGY, ISAT 2019, PT III: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019 - Part III. ред. / Z Wilimowska; L Borzemski; J Swiatek. Том 1052 Cham : Springer Nature, 2020. стр. 188 -198 (Advances in Intelligent Systems and Computing; Том 1052).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Single Machine Scheduling with Precedence Constrains, Release and Delivery Times
AU - Grigoreva, Natalia
N1 - Grigoreva N. (2020) Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. In: Wilimowska Z., Borzemski L., Świątek J. (eds) Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. ISAT 2019. Advances in Intelligent Systems and Computing, vol 1052. Springer, Cham
PY - 2020/1/1
Y1 - 2020/1/1
N2 - The goal of this paper is to propose algorithms for scheduling problem, where set of jobs performed on a single processor. Each job has a release time, when it becomes available for processing, a processing time and a delivery time. We study the case in which there exist precedence constrains among jobs and preemption is not allowed. The objective is to minimize the time, by which all jobs are delivered. The single machine scheduling problem is one of the classic NP-hard optimization problems, and it is useful in solving flowshop and jobshop scheduling problems. We develop branch and bound algorithm for the problem. We propose an approximation algorithm to find an upper bound, solve the preemptive version of the problem to provide a lower bound and use a binary branching rule, where at each branch node, a complete schedule is generated. To illustrate the effectiveness of our algorithms we tested them on randomly generated set of jobs.
AB - The goal of this paper is to propose algorithms for scheduling problem, where set of jobs performed on a single processor. Each job has a release time, when it becomes available for processing, a processing time and a delivery time. We study the case in which there exist precedence constrains among jobs and preemption is not allowed. The objective is to minimize the time, by which all jobs are delivered. The single machine scheduling problem is one of the classic NP-hard optimization problems, and it is useful in solving flowshop and jobshop scheduling problems. We develop branch and bound algorithm for the problem. We propose an approximation algorithm to find an upper bound, solve the preemptive version of the problem to provide a lower bound and use a binary branching rule, where at each branch node, a complete schedule is generated. To illustrate the effectiveness of our algorithms we tested them on randomly generated set of jobs.
KW - Single processor · Branch and bound algorithm · Release and delivery time · Precedence constrains
KW - Single processor
KW - Branch and bound algorithm
KW - Release and delivery time
KW - Precedence constrains
KW - ALGORITHM
KW - DATES
KW - SUBJECT
UR - http://www.scopus.com/inward/record.url?scp=85072840136&partnerID=8YFLogxK
UR - http://www.mendeley.com/research/single-machine-scheduling-precedence-constrains-release-delivery-times
U2 - 10.1007/978-3-030-30443-0_17
DO - 10.1007/978-3-030-30443-0_17
M3 - Conference contribution
SN - 9783030304423
VL - 1052
T3 - Advances in Intelligent Systems and Computing
SP - 188
EP - 198
BT - INFORMATION SYSTEMS ARCHITECTURE AND TECHNOLOGY, ISAT 2019, PT III
A2 - Wilimowska, Z
A2 - Borzemski, L
A2 - Swiatek, J
PB - Springer Nature
CY - Cham
ER -
ID: 47653562