On-line Scheduling A Batch Processing System To Minimize Makespan Using Restarts

In this paper, we consider an on-line scheduling problem that in a batch processing system, jobs in a batch are allowed to restart. Our model can be represented as:l|on-line, r_j; p-batch, b =∞; restarts |C_max.On-line, we here mean that jobs arrive over time, and all job characteristics (including arriving times)are unknown before their arrival time. Jobs cannot be scheduled before they arrived, and jobs do not have to be scheduled immediately upon arrival. Once they are scheduled the schedule cannot be changed. In the model, parallel batch is one of the simultaneous processing models. It means that several jobs can be processed on a machine as a batch at the same time. The starting times and completion times of jobs in a batch are equal, respectively. The processing time of a batch is equal to the longest processing time of jobs, and the completion time of a batch is the completion time of a longest job in the batch. Parallel batch problems can be devided into two catalagues: those of the unbounded capacity and the bounded capacity. We here consider the unbounded capacity case, that is, we can process sufficiently large number of jobs at the same time.In the following, we give the definition of restart. A job allowed restarts means that the processing of the job can be interrupted and let the machine process other jobs, and later we have to start this interrupted job from scratch. That is to say, the time spent on the job before interruption is wasted. Being different from a job's restarts, a batch allowed restarts 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 practice, the scheduling needing restarts is widely seen, such as in metal refinery, burn-in operations in semiconduct manufacturing, running a program on a computer, downloading a file from the internet and so on. The products in those situations require continuous processing with no interruption; if they were interrupted, they must be...