Some Problems Of Online Scheduling To Minimize Flow-time

In the classical problems of scheduling, people considered how to schedule jobs, the information of which is known before being arranged. With the progress of studying, we get another kind of problems called online scheduling in which information of jobs is un-known before arrival. Many former papers have always concerned objective functions like minimizing makespan or total completion times of jobs. Here we mainly study problems of online scheduling but with an objective function concerning the flow-time of jobs. We consider a job J, using C and r to denote its completion time and its arrival time, re-spectively. Therefore, the flow-time of job J can be defined to be F = C - r. The job J has a delivery time q, so we introduce a new objective function denoted by DF, where DF = F + q for job J. There jobs can be processed in batches, and all jobs in a batch have the same starting time and the same makespan, respectively.In this paper, with three-field notation, we study three problems which can be denoted as follows:(1) Pm| online, p-batch, b, pj = 1, qj| DFmax.(2) Pm| online, p-batch, b ? n, job families, f, pj = 1| Fmax.(3) 1| online, p-batch, b ? n, lookahead, 0 ? L ? 1, pj = 1| Fmax.In the first problem, online scheduling that is on m identical parallel machines con-cerning the unit length jobs with delivery times is considered. This problem is about to minimize DFmax. In the second chapter, we get the results of different circumstances. We use b to denote the capacity of each batch. When b ? n, we provide an online algorithm of competitive ratio 1 + ?m which is best possible, where ?m satisfies x2 + mx = 1. When 1 < b < n, we provide an online algorithm of competitive ratio 1.618 which is best possible.When b = 1, m = 1, the ratio is 1.414 which is best possible by an online algorithm.In the second problem, unbounded version and incompatible families of unit-length jobs are considered, and the jobs which belong to different families cannot be processed in one batch. The objective is to minimize maximum flow-time. We use f to denote the number of incompatible families. In the third chapter, we mainly study two special models. When m = 1, f = 2, we give a best possible online algorithm with a competitive ratio 1.618. When m = af, a best possible online algorithm of competitive ratio ?a is provided, where ?a satisfies x2 + (a + 1)x = 1.In the third problem, we consider unbounded version and unit jobs with lookahead online scheduling on a single machine. Lookahead means we can foresee the information of jobs in a certain time interval and we use L to denote the length of this time interval.And the objective is also to minimize maximum flow-time. We give a best possible onlinealgorithm which has a competitive ratio 1+?L= (?) where a satisfiesx2 + (2 + L)x + L-1 = 0.