| In this thesis, we mainly study two semi-online scheduling problemson parallel identical machines. One is scheduling with machine cost, the other is scheduling with non-simultaneous machine available time.The thesis consists of three chapters.In Chapter 1, we give a belief introduction for scheduling problems. Then in Chapter 2, we investigate List Model in two different semi-onlineconditions-he largest processing time known in advance or the totalprocessing time known in advance. For the largest processing time known in advance, we present a semi-online algorithms with competitive ratio at most 15 61/2/24≈1.5309 while the low bound is 4/3. And for the total processing time known in advance, we present a semi-online algorithms with competitive ratio 21/2 while the low bound is 1.161. In Chapter 3, we consider parallel machine scheduling problem with non-simultaneous machine available time and the object is to maximize the earliest machine completion time. In online version, we prove the competitive ratio of LS is Mm. Then in the rest of Chapter 3, we investigate three differentsemi-online conditions-the largest processing time known in advanceor the total processing time known in advance or the jobs ordered in non-increasing processing time. For each problem, we present optimal algorithm (competitive ratio 2/3, 2/3, 3/4) for two machines case.
|
PDF Full Text Request