Title of article
Single machineschedulingtominimizemaximumlatenesssubjecttorelease dates andprecedenceconstraints
Author/Authors
Zhixin Liu، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2010
Pages
7
From page
1537
To page
1543
Abstract
This paperconsiderstheproblemoffindinganonpreemptivescheduleforasinglemachinetominimize
the maximumlatenesswithreleasedatesandprecedenceconstraints.Abranchandboundalgorithmis
developed.Thealgorithmusesfourdifferentheuristicstofindupperboundsattheinitialbranchnode:
early releasedateheuristic,modifiedSchrage’sheuristic,heuristicBLOCK,andavariableneighborhood
descentprocedure.Ateachbranchnode,twobranchesevolvefromaschedulefoundbyheuristicBLOCK
using abinarybranchingrulebasedonbottleneckandcriticaljobs,andalowerboundisobtainedby
optimallysolvingtherelaxedproblemwithpreemption.Thealgorithmsolves14,984outofthe15,000
systematicallygeneratedinstanceswithupto1,000jobswithin1minuteofCPUtime.
Keywords
Precedence constraint , Branch and bound algorithm , Deterministic scheduling , Release date , Maximum lateness
Journal title
Computers and Operations Research
Serial Year
2010
Journal title
Computers and Operations Research
Record number
927762
Link To Document