A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property |
| |
Authors: | Sang-Oh ShimAuthor Vitae Yeong-Dae Kim |
| |
Affiliation: | Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Yusong-gu, Daejon 305-701, Korea |
| |
Abstract: | We focus on the problem of scheduling n independent jobs on m identical parallel machines with the objective of minimizing total tardiness of the jobs considering a job splitting property. In this problem, it is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We develop several dominance properties and lower bounds for the problem, and suggest a branch and bound algorithm using them. Computational experiments are performed on randomly generated test problems and results show that the suggested algorithm solves problems of moderate sizes in a reasonable amount of computation time. |
| |
Keywords: | Scheduling Parallel machines Job splitting Total tardiness Branch and bound |
本文献已被 ScienceDirect 等数据库收录! |