Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Branch and Bound algorithm for Single Machine Scheduling Problem with Release and Delivery Times. / Grigoreva, Natalia.
IX International Conference on Optimization and Applications (OPTIMA 2018) . DEStech Publications Inc, 2019. (DEStech Transactions on Computer Science and Engineering).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Branch and Bound algorithm for Single Machine Scheduling Problem with Release and Delivery Times
AU - Grigoreva, Natalia
PY - 2019
Y1 - 2019
N2 - 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. The goal of this paper is to prepare algorithms for the scheduling problem, where set of tasks is performed on a single processor. Each task has a release time when it becomes available for processing, a processing time and a delivery time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. Preemption is not allowed. The objective is to minimize the time, by which all tasks are delivered. We compare the nondelay schedule, in which no processor is kept idle at a time when it could begin processing a task and an inserted idle time schedule, in which a processor is kept idle at this time. In this paper, we propose an approximation algorithm and by combining this algorithm and branch and bound method, we develop branch and bound algorithm, which can find optimal solutions for the single processor scheduling problem. We 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 tasks.
AB - 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. The goal of this paper is to prepare algorithms for the scheduling problem, where set of tasks is performed on a single processor. Each task has a release time when it becomes available for processing, a processing time and a delivery time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. Preemption is not allowed. The objective is to minimize the time, by which all tasks are delivered. We compare the nondelay schedule, in which no processor is kept idle at a time when it could begin processing a task and an inserted idle time schedule, in which a processor is kept idle at this time. In this paper, we propose an approximation algorithm and by combining this algorithm and branch and bound method, we develop branch and bound algorithm, which can find optimal solutions for the single processor scheduling problem. We 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 tasks.
KW - Single processor
KW - Branch and bound algorithm
KW - Inserted idle time
UR - http://dpi-proceedings.com/index.php/dtcse/article/view/27919
UR - http://dpi-proceedings.com/index.php/dtcse/issue/view/327/showToc
U2 - 10.12783/dtese/optim2018/27919
DO - 10.12783/dtese/optim2018/27919
M3 - Conference contribution
SN - 9781605955872
T3 - DEStech Transactions on Computer Science and Engineering
BT - IX International Conference on Optimization and Applications (OPTIMA 2018)
PB - DEStech Publications Inc
T2 - IX INTERNATIONAL CONFERENCE ON OPTIMIZATION AND APPLICATIONS
Y2 - 1 October 2018 through 5 October 2018
ER -
ID: 39329338