A Study Of Scheduling On Parallel Machines With Activation Cost

This thesis mainly concerns design and analysis of approximation algorithms for(semi-)online parallel machine scheduling problems with machine activation cost. Foreach problem considered in this thesis, both lower bound and (semi-)online approx-imation algorithms are provided. Here, we are given m potential machines to non-preemptively process a sequence of independent jobs. Machines are need to be ac-tivated before starting to process, and each machine that is activated incurs a fixedmachine activation cost. No machines are initially activated, and when a job is revealedthe algorithm has the option to activate new machines. The objective is to minimize thesum of the makespan and activation cost of machines.The thesis is split up into six chapters. We first introduce some preliminary con-cepts and necessary knowledge about combinatorial optimization and scheduling prob-lems in Chapter 1 and 2. And also some results of (semi-)online scheduling are pro-vided.In Chapter 3, we first consider online scheduling problems on identical machineswith activation cost. We present two optimal online algorithms with competitive ratiosof 3/2 and 5/3 for m=2, 3 cases, respectively. Then we present an online algorithm witha competitive ratio of at most 2 for general m≥4, while the lower bound is 1.88.In Chapter 4, we investigate online scheduling problems with activation cost ontwo uniform machines with speeds 1 and s. We design optimal online algorithms withcompetitive ratio of 2s+1/s₁ for all values of s.In Chapter 5, we investigate semi-online scheduling problems with activation cost.For the semi-online problem with known the sum size of all jobs P in advance, wepresent a semi-online algorithm which is optimal for every P＞0. For the problemwith known the largest size of all jobs L in advance, we present an optimal semi-onlinealgorithm for every L＞0.