Two Kinds Of Online Scheduling On Single Bounded Batch Machine

In this paper, we study the on-line scheduling problem on a bounded batch machine. We suppose that all jobs have their processing times in [p,(1+Φ)p], where p>0.In this paper, the two scheduling problems are denoted as:(1)1|p-batch, online (2)1|p-batch, online For the first model:We consider an online scheduling problem in a parallel batch processing system with jobs in a batch being allowed to limited restarts. The objective of the problem considered in this paper is to minimize the maximum completion time.A batch allowed restart means that we may interrupt the running batch and the completed part is wasted, then jobs in the interrupted batch are released and they become independently unscheduled jobs. Each of them can form new batch with other jobs which have arrived and have not been scheduled, and then they were scheduled again. Allowing restarts reduces the impact of a wrong decision.In this paper, limited restart means any batch which contains interrupted jobs cannot be restarted any more. For the scheduling problem1|p-batch, online Cmax,Fang et al.[3] give a best possible online algorithm with competitive ratio where Adding a condition that batchs are allowed restarts to above model, we get the model studied in this paper.We prove that the lower bound of any online algorithm for this scheduling problem is not less than3/2, and provide a best possible online algorithm with competitive ratio3/2. For the second model:We study a single batch machine online scheduling problem with delivery time. The objective is to minimize the time by which all jobs have been delivered, where Dmax=max{For the scheduling probleml|p-batch, online, B give a best possible online algorithm with competitive ratio (?). In this paper, we consider this problem using We prove that the lower bound of any on-line algorithm for this scheduling problem is not less than and provide a best on-line algorithm with competitive ratio (?).