On-line Scheduling With Delivery Time On A Single Batch Machine

Scheduling is to assign some tasks to time resources under some constraints, such that one- or multi-criteria attain to the optimum. Recently, on-line scheduhng and parallel batch scheduling are two flourishing scheduling models. On-line scheduling means that all job informations are unknown before their release times, and once a job is scheduled it cannot be changed. Parallel batch scheduling means that a machine can process several jobs simultaneously as a batch, and the processing time of the batch is equal to the longest processing time of the jobs assigned to it. Once a batch is started, it cannot be stopped until its completion.In our paper, we consider an on-line scheduling model: on-line scheduling with delivery time on a single batch machine. Here, we have a batch machine and sufficient vehicles. There are n jobs J₁, J₂,..., J_n. Each job has a release time rj, a processing time pj, and a delivery time qj. These informations are known about a job until it arrives . In this problem , each job needs to be processed on the machine, and once the job is completed we deliver it to the destination by a vehicle. Our objective is to minimize the time by which all jobs have been delivered. Using the 3-field notation of Graham et al.[4], our problem is denoted as 1|on-line, rj, qj, B|D_max, where D_max= max{Dj|Dj = Cj + qj, 1 ≤ j ≤ n}.The main results of this paper are as follows.(1) For the scheduling model 1|on-line,rj,qj, B = ∞|D_max, we give an on-line algorithm with competitive ratio not greater than 2.(2) For the scheduling model 1|on-line,rj,qj,Pj = p,prec,B = ∞|D_max, we give an on-line algorithm with competitive ratio not greater than ((?)5 + 1)/2, and it is a best possible on-line algorithm.(3) For the scheduling model 1|on-line, rj, qj, B < n|D_max, we give an on-line algorithm with competitive ratio not greater than 3.(4) For the scheduling model 1|on-line,rj,qj,pj = p,B < n|D_max, we give an on-line algorithm with competitive ratio not greater than ((?)5 + 1)/2, and it is a best possible...