Research On Some Semi-online Scheduling Problems Under LP-norm

In this paper, we focus on semi-online scheduling problem under Lp-norm. Given a set of identical machines and a list of jobs arriving one by one, the task is to arrange each arrive jobs to a machine, such that no two time intervals overlap on the same machine and no two time intervals allocated to the same job overlap, we call such allocation a feasible schedule, the objective is to minimize the 1p norm of machines complete time vector.In online version with job arriving over list, only when the current job is allocated, the next job can be coming, and only when each job arrived, we can know all the information about the job . Each job can not interrupt before it finished. When we know some partial information of jobs, we call it semi online scheduling. In this thesis, we focus on semi online scheduling. The main contribution is as follows.First, we consider the semi-online scheduling of jobs on three identical machines with known the sum of the total process times. We proposed a semi-online algorithm with competitive ratio at most max {3/2,(?)}Secondly, we consider the semi-online scheduling of jobs on three identical machines with known the longest process time. We proposed a semi-online algorithm with competitive ratio at most max {(?),(?)}Finally, we consider the parallel job scheduling on m identical machines under 1p norm in chapter 5. We present a semi-online algorithm with competitive ratio at most 40/3 for the case that the longest process time is known.