Design And Analysis Of Reclaimer Scheduling In Terminal Yard

Bulk material storage yard,as the interface between inland transportation and sea transportation,plays an important role in export business.In particular,the advantages of continuous operation of stacker and reclaimer in the yard area and the ability to carry out bulk material stacking and reclaiming make it occupy an important position.This thesis studies an abstract scheduling problem that arises in the yard management of a coal terminal.The goal is to determine the stacking position of bulk materials on the yard,and to sort the recycling order(so does the stacking order),so as to minimize the overall time reclaiming a set of stockpiles.We approach this problem by sending a simple NP-hardness proof and proposing polynomial time approximation algorithms.For easy elaboration,we divide the thesis into four chapters.In Chapter 1,we first briefly introduce some basic concepts of scheduling,algorithm and computational complexity.Then we formally define the reclaimer scheduling problem and give some notations and terminology that will be used throughout the thesis.In Chapter 2,we show that the problem is polynomial solvable if the reclaimer is allowed to terminate at any position of the stock pad,and becomes NP-hard if it has to return to the starting end or terminate at either end of the pad.For the latter two cases,we present two approximation algorithms with the same worst case ratio of 1+1/3s for any s(?1),where s is the ratio of the travel speed to the reclaim speed of the reclaimer.Chapter 3 revisits the NP-hard problems mentioned in Chapter 2.Observing a natural correspondence between reclaimer scheduling and parallel machine scheduling,we succeed to design an improved algorithm to solve problem,which has a worst case ratio of 1+1/4s.Finally,Chapter 4 summarizes the thesis and makes conclusion.