《物流系统分析与优化》课程教学课件（PPT讲稿）Quay Crane Scheduling

Quay Crane Scheduling

Quay Crane Scheduling

Quay Crane Scheduling with Non-lnterferenceconstraints Problem (QCSNiP) for single containervessel·Assumptions:Quay cranes are on the same track and thus cannot cross over each other.: Only one quay crane can work on a hold at a time until it completes the hold.:Compared with processingtimeof a hold bya quay crane, travel time of aquay cranebetween two holds is small and hence it is ignored

Quay Crane Scheduling with Non-Interference constraints Problem (QCSNIP) for single container vessel • Assumptions • Quay cranes are on the same track and thus cannot cross over each other. • Only one quay crane can work on a hold at a time until it completes the hold. • Compared with processing time of a hold by a quay crane, travel time of a quay crane between two holds is small and hence it is ignored

Land sideQuay-KcraneThe front of theThetailofthecontainervesselcontainervessel2H1H-1HoldContainervesselSea sideK:Thenumber ofquaycranesH:Thenumberof holds

ParametersKthe number ofquay cranes;Hthe number of holds:theprocessingtimeof hold hbya quay crane(l≤h<H);PhMa sufficientlylarge positive constantnumber

Parameters

Decision variablesXh.k1,if holdh ishandledbyquaycranek,O,otherwise(1≤h<H,1<k<K);Yh.nI, if hold h finishes no later than hold h'starts;O,otherwise(l≤h,h'≤H);Chthecompletiontimeofholdh(l<h≤H)

Decision variables

(1)maxChhSubject to:(2)VI0VI≤h,h≤H(5)Ch-(CH-PH)-(1-YhR)M≤0VI≤h,h≤HKKM(YHH+YRA)≥EKXhK-iX+1(6)VI≤h<h≤Hk=1(7)X,Y=oorIVl≤h,H≤H,VI<k≤K

The objective function (l)minimizes the makespan of handling one single container vessel, which is the latestcompletion timeamongall holds.Constraints (2)definetheproperty of thedecision variable Ch.Constraints(3)ensurethat everyholdmustbeperformedonlybyonequaycrane.Constraints(4)and(5)definetheproperties ofdecisionvariables Yh.w:Constraints (4)indicate thatYh,= if C,≤Cw-pw,whichmeans Yh=1when hold h finishes no later than hold h'starts; Constraints (5)indicate that Yh=0 if Ch>Cw-Pw,whichmeans Yh=O when hold h finishes after hold h'starts.Finally,the interference between quay cranes can beavoided by imposing Constraints(6).Suppose thatholds hand h'areperformed simultaneouslyand h<h',then this means that Yhu + Yw',h = o. Note that both quay cranes and holds are arranged in an increasing or-der from the front to the tail of the container vessel.Thus, if quay crane k handles hold h and quay crane!handlesholdh,thenk+I≤l

.Theproposed QcsNiP isproved to beNP-complete,meaningthatthere exists no polynomial time algorithm for its exact solution

• The proposed QCSNIP is proved to be NP-complete, meaning that there exists no polynomial time algorithm for its exact solution

GA·Solutionrepresentation:Intheformofchromosomerepresentingthesequenceofholds:A procedure is needed to develop the correspondingquay crane schedule

GA • Solution representation • In the form of chromosome representing the sequence of holds • A procedure is needed to develop the corresponding quay crane schedule

Step l:Based on the current position of each quay crane,determine which quay cranes can handlethe firstunassigned hold in the chromosome without interference with the other quay cranes.If there is onlyonequay crane available, this hold is assigned to this quaycrane.Then, this hold is deleted from thechromosome, and the position and the completion time of the assigned quay crane are updated.Iftherearetwoquaycranesavailable,goto Step2.Step 2:Compare the completion time of the two available quay cranes to finish their assigned holds, andassign this hold to the quay crane with earlier completion time.Then,this hold is deleted fromthe chromosome, and the position and the completion time of the assigned quay crane are updated.Iftheircompletiontimeisequal,gotoStep3.Step3:Comparethe distancebetween thishold and thesetwoavailablequay cranes,and assign this hold tothe quay crane with the shorter distance. Then, this hold is deleted from the chromosome, and theposition and the completion time of the assigned quay crane are updated.If their distance is equal,goto Step4.Step 4:Assign this hold to the quay crane with the smaller number.Then, this hold is deleted from the chro-mosome, and the position and the completion time of the assigned quay crane are updated.Step5:Steps 1-4arerepeateduntil alltheholdsin thechromosomeareassigned