A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property

A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property

0.00 Avg rating0 Votes
Article ID: iaor2009972
Country: United Kingdom
Volume: 35
Issue: 3
Start Page Number: 863
End Page Number: 875
Publication Date: Mar 2008
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: branch and bound
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.

Reviews

Required fields are marked *. Your email address will not be published.