| This paper mainly studies two semi-online scheduling problems. In Chapter 1, we introduce some basic notions: combinatorial optimization, scheduling problems, algorithm and competitive ratio. Then we summarize the models of different semi-online scheduling problems and the results of them.In Chapter 2, we give an introduction for two preemptive semi-online scheduling problems to maximize the minimum machine completion time on two identical machines. In the second section, we investigate the first semi-online problem — it is known in advance that all jobs have their processing times in between p and rp(p > 0,r ≥ 1). Forevery r ≥ 1, we design an optimal semi-online algorithm. The competitiveratio of the algorithm is at most (4+r)/4 when 1 ≤ r < 2, and at most -when r ≥ 2. In the third section, we consider the semi-online problem that it is known the size of the largest job in advance, and then propose anoptimal semi-online algorithm with competitive ratio 5/4.
|
PDF Full Text Request