Scheduling Problems Under The L_p Norm On Two Identical Machines

This paper mainly studies online and semi-online scheduling problems on two identical machines. Given a sequence J = {p₁,P₂, ··· ,P_n} of independent jobs, each with a positive processing time (size) p i,i= 1,···, n, which must be non-preemptively scheduled on one of the two identical machines M₁, M₂. The load of a machine is the total size of the jobs assigned to it. The load of i-th machine related to an algorithm S is denoted by l_i(J, S)(l_i) ,i=1,2, respectively. The objective is to minimize the sum of the l_p norm of machine's load, i.e., L_P(J, S) = [l₁(J, S)^p + l₂(J, S)^p]^1/p, where p > 1 (Note that for p = 1, the problem is trivial and any algorithm yields an optimal solution). The paper consists of three chapters.Chapter 1 gives some introduction and preliminaries for scheduling problems.Chapter 2 investigates the semi-online scheduling problem under the l_p norm on two identical machines, where jobs come in non-increasing order of their sizes. We prove that algorithm LS is optimal for any l_p norm with competitive ratioFurthermore, randomized lower bounds are presented forthis problem and related online problem.Chapter 3 considers other two semi-online scheduling problems under the l_p norm on two identical machines. For the problems where the maximum processing time of the jobs and the total size of all jobs is known in advance, respectively. We present optimal algorithms with the same competitive ratio...