Research On Parallel Machines Scheduling With Servers

Parallel machine scheduling with servers has application in flexible manufacturing.In this thesis,we mainly investigate parallel machine scheduling problems with a loading server and a unloading server.The goal is to minimize the maximum completion time.We analyse the worst-case ratios of LS classical algorithms and LPT classical algorithms for two-machine case and three-machine case.The thesis is divided into five chapters.In the first chapter,we briefly introduced the basic knowledge of the scheduling problem,the related background and results of the problems studied in our thesis.In the second and third chapters,we study two parallel-machines scheduling problem with a loading server and an unloading server.Each job is loaded onto one of the two machines by the loading server before its processing.After the processing is finished,it is unloaded from the machine by the unloading server.Both the loading and unloading time are equal to unit time.The goal is to minimize the maximum completion time.In the second chapter,we show the LS algorithm has a tight worst-case ratio of₇¹¹.In the third chapter,we show the LPT algorithm has a tight worst-case ratio of₆⁷.The results are improvement of the previous results.In the fourth chapter,we study three parallel-machines scheduling problem with a loading server and an unloading server.We show that the worst-case ratio of the LS algorithm is at most₉¹⁷.Chapter 5 summarizes the thesis and suggest future research topics.