| Machine scheduling and covering problems may occur in many applications such as load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc. In this thesis, we study the semi-online machine covering problem on m parallel identical machines, the goal is to maximize the minimum machine load. We study several models and for each model we give lower bounds and present semi-online algorithms, which are optimal in some cases. The thesis consists of four chapters.In chapter 1, we gives some introduction and basic knowledge for scheduling problems.In chapter 2, we studies semi-online versions of Pm||Cmin with the total processing time of all jobs or the largest processing time of all jobs is known in advance. We will present optimal algorithms for Pm|sum|Cmin and Pm|max|Cmin respectively. The competitive ratios of two algorithms are both m — 1.In chapter 3, we considers problems Pm|sum & max|Cmin and Pm|opt & max |Cmin. For the model Pm|sum & max|Cmin, we will give optimal algorithms for m ≥ 3. The competitive ratios of the optimal algorithms are 3/2 if m = 3, and m - 2 if m ≥ 4. For Pm|opt & max|Cmin, we present an optimal algorithm OM2 with competitive ratio 5/4 for two machine case and algorithm OMm with competitive ratio 2 - 1/(m-1) for m ≥ 3 machine case, which is optimal when m = 3,4,5.In chapter 4, we investigates problems Pm|k - bounded|Cmin and Pm|opt & k -bounded|Cmin. We first prove that LS is an optimal algorithm for Pm|k — bounded|Cmin with competitive ratio mk/(mk-m+1) For Pm|opt & k - bounded|Cmin, we prove that the lower bound is (2k+1)/2k when m ≤ 2k + 1 or m/(m-1) when m > 2k + 1. And the competitive ratio of kFillm is (mk+m-1)/mk.
|
PDF Full Text Request