Scheduling Problems Of Parallel Machine With Loading And Unloading

In this thesis, we study the scheduling problem in which jobs are processed on twoidentical parallel machines that share servers which loads and unloads jobs on them. Forthis kind of problem, the general research is that the server only charge the loading operation.But along with the development of automation, it is worthy of study in the actual productionoperation that each job has to be loaded by a server before being processed on the machineand unload immediately by a server after its processing. Due to the increase of one operation,it is also increase the difculty in algorithm design. So, frst, we study a preemptive variantwith only one server. Second, we study a non-preemptive variant with two servers. Third, weintroduce a practical application: a scheduling problem about parcels that is very commonin the distribution center. The Longest Processing Times(LP T) algorithm is presented tosolve this problem. We compare the results between the random algorithm R, LP T and theoptimal algorithm and fnd LP T can solve this problem efectively.The thesis is organized as follows:In chapter1, we briefy introduce the basic theory and background of the scheduling,algorithm design and analysis of the scheduling problem. By using worst case ratio tomeasure the efectiveness. And we also briefy introduce the research status about schedulingproblems with common serves at home and abroad.In chapter2, we study the preemptive variant with only one server with the object tominimize the makespan. Each job has to be loaded by the server before being processedon one of the machine and unloaded by the server after its processing. The loading andunloading times are both equal to one time unit. We design an optimal algorithm OP A tosolve this problem.In chapter3, we study a non-preemptive variant with two servers with the object to min-imize the makespan. One of the two servers load the jobs on one of the two machines beforethe job was processed on the machine and the other server unload the job from the machineafter the job was processed. We apply two classical algorithms, namely list scheduling(LS)algorithm and longest processing time(LP T)algorithm, to tackle this problem. We showthat LS and LP T have worst-case ratios of8/5and6/5, respectively. In chapter4, we study a scheduling problem about parcels that is very common inthe distribution center. Because the number of unload docks are less than the number ofinbound trailers, efective scheduling of the inbound trailers to the unload docks is essential.An efective scheduling can reduce the cost of operating cost, improve the reliability of thedelivery system, and ultimately enhance the competitiveness of the distribution center. Butit is difculty to fnd the optimal scheduling, if we fnd a scheduling which is close to theoptimal scheduling, we can think it is an efective scheduling. In this chapter, we use LP Tto tackle the problem efectively. Though several examples, we give the schedulings of theparcels by using the random algorithm R and LP T. By achieving the worst case ratio, wefnd that LP T can tackle the problem efectively.In chapter5, we mainly give some remarking conclusions about the future study.