On-line And Semi On-line Scheduling For Jobs With Release Times On Parallel Machines

This thesis is composed of three chapters. It focuses on some models of on-line scheduling or semi-online scheduling on parallel machines for jobs with release times and mainly analyze the LS algorithm competitive performance ratio.The introduction of the background and history of scheduling problem and competitive ratio analysis, approximation algorithms is briefly addressed in Chapter 1. A brief summary of online models and their results which appeared in recent years is given.In Chapter 2, we study the semi on-line scheduling on Identical Machines for jobs with arbitrary release times. we assume that the list of the processing times of all jobs corresponding to job list L are non-increasing,i.e.,p1≥P2>…≥Pn.The objective is to find a schedule to minimize the makespan. We proved that algorithm LS has a ompetitive ratio of 2-(1/2m) and we also showed that this is a tight bound when m=1.In Chapter 3, we consider the on-line scheduling on Uniform Machines for jobs with non-decreasing release times and arbitrary processing times. It is assumed that Mi has a speed si,where si=1(1< i< m - 1), sm= s> 1.The objective is to find a schedule to minimizes the makespan. We proved that the algorithm LS has a competitive ratio of 2 for m=2 and a upper bound of min for general m machines.