Semi On-line Parallel Machine Scheduling Problems

This paper studies semi online parallel machine scheduling problems. In the first we introduce basic notions of scheduling problems, competitive analysis and approximation algorithm, summarize semi online models and their results which appear in recent years.In Chapter 2, we investigate semi online scheduling problems where the largest processing time of all jobs is known in advance. The goal is to maximize the minimum machine completion time. In this chapter, we mainly consider two problems: 1 For the case of three uinform machines, we present min3 algorithm and show its competitive ratio is max{r + 1,3s+r+1/+r+s} which is tight and optimal for 1 ≤ s ≤ 2 , r = 1.2 For a special case of m uniform machines, we provide Cmin algorithm and show its competitive ratio is max{m- 1, ms+m-1/m-1+s} which is tight and optimal for 1 ≤ s ≤ (m - l)(m - 2)(m ≥ 3).In Chapter 3, we consider the semi online scheduling problems where the largest processing time of all jobs is known in advance. The objective is to minimize the maximum machine completion time. We mainly consider four problems: 1 We give Qmax2 algorithm whose competitive ratio is 2(s+1)/s+2 (1≤ s≤ 2) and s+1/s (s > 2) for two uniform machines case, and show Qmax2 algorithm is tight and optimal for some s. 2 For the case of three uniform machines, we present Qmax3 algorithm whose competitive ratio is not greater than 2(r+s+1)/2r+s(1 < s ≤ 2) and r+2s+1/r+s (s > 2) but strictly less than 2.3 If the machine are three special machines, we provide Qmax3t algorithm whose competitive ratio is not greater than s+2/2 (1 ≤ s ≤ 2) and s+2/s (s > 2) but strictly less than 2. 4 Finally, we investigate m identical parallel machines case. We give Cmax algorithm and show its competitive ratio is 2m-3/m-1 which is tight for every m≥3.In Chapter 4, we study such scheduling problem where the total processing times of all jobs is known in advance on two uniform machines with objective to maximize the minimum machine completion time. We propose Q2min algorithm and show its competitive ratio is less than 2+(?)2/2, while the lower bound is 1+(?)5/2. We also prove the Q2min algorithm is optimal for s = 1+(?)5/2 case.In Chapter 5, we consider semi online scheduling problem where the total processing time is known in advance with nonsimultaneous machine available times. In the first section, we investigate P2,ri|sum|Cmin problem. We present Prsum algo-...