| Scheduling is one of the most active fields of operational research, and a large amount of scheduling models under different machine environments have been studied. Accord-ing to jobs' different properties, scheduling problems are divided into off-line scheduling problems and on-line scheduling problems. In off-line scheduling problems, all the jobs'information is known before a scheduling decision is made. However,in this paper, we s-tudy some kinds of standard online scheduling problems, which mean that jobs arrive over time and each job's characteristics,including release date, processing time and so on, are unknown until it is released. In the LK? model, at a time instant t, an on-line algorithm can foresee the information of all jobs arriving in the time segment (t, t+?]. Incompatible job families mean that jobs which belong to different families cannot be assigned to the same batch.Batch-scheduling models go into two categories by the way of batching: parallel-batch scheduling and serial-batch scheduling. In the parallel-batch (p-batch) model, several jobs can be processed on a machine as a batch at the same time. The starting time and completion time of jobs in a batch are equal, respectively. The processing time of a batch is given by the longest processing time of the jobs in the batch. In the serial-batch (s-batch)model, the jobs in a batch are processed serially and their completion times are defined to be the finishing time of the last job in the batch. The processing time of a batch is defined by the total processing time of the jobs in it. The batch capacity b means that there are at most b jobs can processed in a batch. There are two versions: the bounded case and the unbounded case.In this paper, we research some special online scheduling problems on batch machines.The scheduling problems are denoted as follows:(1) 1|online,p-batch,pj =1,b=?,LK?|Dmax(= maxj {Cj+qj});(2) 1|online, p-batch, pj = 1,b = ?,f-family|Dmax(= maxj{Cj + qj});(3) Pm|on-line,s-batch|Fmax(= maxj{Cj- rj})The description of the first model:In this problem, we consider on-line scheduling problem on a unbounded parallel-batch machine with lookahead and delivery time of unit-length jobs. The objective is to minimize the completion time by which all jobs have been delivered. For the model considered in this paper, in section 2, we established a online algorithm. If 0???1/6, the algorithm is the best possible algorithm with a competitive ratio of 1 +?a*, where ?* =?is the positive root of the equation ?2 + (? + 1)? + ?-1= 0. If ?>1/6, the competitive ratio of the algorithm is 1 + ?* = 3/2.The description of the second model:In this problem, we consider on-line scheduling problem of f incompatible unit-length job families on a unbounded parallel-batch machine. The objective is to minimize the completion time by which all jobs have been delivered. For the model considered in this paper, in section 3, we give a best possible online algorithm with a competitive ratio of 1+?f, where ?f is the positive root of the equation f?f2+?f-f= 0.The description of the third model:In this problem, we consider on-line scheduling problem on a serial-batch machine.The objective is to minimize the maximum flow-time. In section 4, for the problem Pm|on-line, s-batch|Fmx when m?2, we give an online algorithm with a competitive ratio of 1 +?m, where ?m is the positive root of the equation ?m2+ (m + 1)?m=1;when m = 1, we offer an online algorithm with a competitive ratio of 1 +?, where?=(?);while for the problem Pm|on-line, s-batch,pj=1|Fmax,we give an online algorithm with a competitive ratio of 1 + ?m, where ?m is the positive root of the equation(s + 1)?m2+(ms + m+ s + 2)?m - s = 0, and ?m> 0. When m = 1, we try to offer an algorithm H1 with the competitive ratio of 2, and we can not achieve a better competitive ratio than 2 when m ? 2. |
PDF Full Text Request