Semi-online Machine Scheduling On Two Uniform Machines Under The1p Norm

In this thesis, we consider some semi-online scheduling problems on two uniform machines under the Ip norm. The problem can be described as follows:Given two uniform machine with different speed s1, s2, and a job sequence arriving online over a list, every arrived job must be scheduled on one of the two uniform machines non-preemptively, only after current job scheduled, the new job will be arriving. The objective is to minimize the Ip norm of the machines load.After given a short introduction of the scheduling theory, we study the semi-online version of knowing the maximum processing time of the jobs in the second chapter, we proposed an online algorithm with better competitive ratio, we prove that the ratio is at most CA≤max{α, β), WhereIn chapter3, we study the case of knowing the total size of the jobs. We proposed an online algorithm with better competitive ratio, we prove that the ratio is at most CA≤max{α, β}, WhereAt last, we study the scheduling problem of knowing the maximum processing time and the total size of the jobs. We proposed an online algorithm with better competitive ratio, we prove that the ratio is at most CA≤max{α, β}≤2, WhichFinally, we give a summary of the thesis and some advices on future research work.