Semi-online Scheduling Algorithm To Predict The Composite Information

Machine scheduling and covering problems may occur in many applications suchas load balancing in network communication channel assignment, parallel processingin large-size computing, task arrangement in flexible manufacturing systems, etc. Inthis thesis, we study the semi-online scheduling problems on m parallel identical machineswith combined partial information. We study the semi-online machine coveringproblem, which was first proposed by Deuermeyer et. al. and has applications in thesequencing of maintenance actions for modular gas turbine aircraft engines and bandwidthallocation on parallel links motivated by issues of QoS. We also consider thesemi-online bin stretching problem, which was first proposed by Azar and Regev, andscheduling with nonsimultaneous machine available times. All problems arise in variousapplications. For each problem, we give lower bounds and present semi-onlinealgorithms, which are optimal in some cases. The thesis is split up into seven chapters.In Chapter 1, we introduce some preliminary concepts related to design and analysisof algorithm.In Chapter 2, we show the models considered in this thesis, and survey the relevantresults of online and semi-online parallel machines scheduling problems. Then wepresent the main results of this thesis.In Chapter 3, we study the semi-online version of scheduling on two parallel identicalmachines, where the total processing time of all jobs and the processing time ofthe largest job are both known in advance (P2|sum & max|C_max). Even though thereexists an optimal semi-online algorithm for P2|sum & max|C_max with competitive ratio6/5, the result is not good, because it was attained when only focus on the worst case.Algorithm with better competitive ratio could be reached for most cases. In this chapterwe focus on such topic: if we can get better algorithms for P2|sum & max|C_max interms of the parameter r = 2p_max/T. For different values of r, we show lower boundsand design algorithms. Both the lower bounds and competitive ratios of the algorithmsare given as functions of parameter r. For the case r = 1/2, we show an optimal algorithmwith competitive ratio 7/6. When (?)≤r≤1 we also design optimal algorithms, the competitive ratio isIn Chapter 4, we consider semi-online version of bin stretching problem, wherewe know that all items will arrive in non-increasing order of their sizes. The goal isto minimize the stretch factor. The problem is also a semi-online scheduling problemwith combined partial information: the off-line optimal value and all items will arrivein non-increasing order of their sizes, the goal is to minimize the makespan. The lowerbound of the problem is at least 10/9 for m machines case. A semi-online algorithm withcompetitive ratio 1+(?) will be shown. An improved algorithm will be also shownfor the special case P3|opt & decr|C_max, and the competitive ratio is at most 7/6.In Chapter 5, we investigate semi-online scheduling problems with k - boundedjobs, which means the upper bound of all jobs is C^*/k. In order to improve the qualityof service, we would like the loads on the machines to be balanced. We measure thebalance by maximizing the minimum machine load or by minimizing the maximummachine load. We first prove that LS is an optimal algorithm for Pm|k-bounded|C_maxwith competitive ratio 1+(?) when m≤k+1. For the case m＞k+1 we show thatthe lower bound is at least 1+(?). For Pm|opt & k - bounded|C_max, lower boundis at least 1+(?). An optimal algorithm OB2 is designed for the two machine case.For the problem Pm|k - bounded|C_min, LS algorithm is an optimal algorithm withcompetitive ratio (?). For Pm|opt & k - bounded|C_min, lower bound is at least1 +(?), where there exists an algorithm with competitive ratio of at most 1 + (?).In Chapter 6, we study the semi-online machine covering with nonsimultaneousmachine available times on three identical parallel machines. We give an optimal algorithmwith competitive ratio 3/2 when we know combined partial information: the totalprocessing time of all jobs and the processing time of the largest job.In Chapter 7, we present a summary of our results, and point out some futureworks in these areas.