Title of article
A branchandpricealgorithmtominimizemakespanonasinglebatch processing machinewithnon-identicaljobsizes
Author/Authors
N. RafieePars، نويسنده , , B.Karimi ، نويسنده , , A.HusseinzadehKashan، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2010
Pages
11
From page
1720
To page
1730
Abstract
In thispaper,weconsidertheschedulingproblemonasinglebatchprocessingmachinewithnon-
identicaljobsizes;inwhichthemachinehasalimitedcapacityandcanprocessagroupofjobs
simultaneouslyasabatch.Theprocessingtimeofabatchisthelongestprocessingtimeofalljobsinthe
batch. Theobjectiveistominimizethemakespan.WeformulatetheproblemusingDantzig–Wolfe
decompositionasasetpartitioningproblem.Basedonthesetpartitioningformulation,wepresenta
tight lowerboundusingcolumngenerationmethod.Aheuristicalgorithmisalsodevelopedtogenerate
the basicsolutioninthecolumngenerationmethod.Abranchandpricealgorithmwhichcombinesthe
column generationtechniquewithbranchandboundmethodisthenpresentedtoobtaintheoptimal
solution oftheproblem.Theefficiencyoftheproposedbranchandpricealgorithmisultimately
comparedtothebranchandboundalgorithmfromtheliterature,basedonthegeneratedsample
problems.
Keywords
Scheduling , Batch processing machine , Makespan , Column generation , Branch and price
Journal title
Computers and Operations Research
Serial Year
2010
Journal title
Computers and Operations Research
Record number
927778
Link To Document