Some Special Models On Batch Scheduling

Recently, parallel batch scheduling and on-line scheduling are two flourishing scheduling models. Parallel batch scheduling means that a machine can process several jobs simultaneously as a batch, and all jobs in a batch start and complete at the same time. The processing time of a 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. On-line scheduling means that all job's information are unknown before their release times, and once a job is scheduled it cannot be changed.In this paper, we mainly consider some special models on batch scheduling. First of all, we investigate the single machine parallel batch scheduling problem with job compatibility constraints and delivery time. Here, we have a batching machine and sufficiently many vehicles. There are n jobs J₁, J₂,…, J_n, each of which has the same processing time p and a delivery time q_j. The jobs can be processed in a batch if and only if they satisfy the relation of compatibility. A batch can be delivered to the destination by a vehicle as soon as it is completed. Our objective is to minimize the time by which all jobs have been delivered. Now we construct a graph G as follows: Consider the jobs J₁,J₂,…,J_n as the vertices of graph G; And join the jobs(vertices) J_i and J_j if they are compatible and can be processed in one batch. It is easy to see that the jobs scheduled in the same batch must be a clique in graph G. We denote this model by1|p-batch;p_j = p, q_j, G|D_max, where D_max =max{D_j|D_j = C_j + q_j,1≤j≤n}. From Zhang Qunfa's dissertation[8], we know 1|p-batch;p_j = p;G|C_max is NP-hard, so the problem we consider is also NP-hard. For some special graphs, we give polynomial algorithms. The main conclusions are as follows:(1) When the graph G is limited to a split graph, we give an optimal algorithm with the running time O(n²).(2) When the graph G is limited to a complete bipartite graph, we give an optimal algorithm with running time O(nlogn). (3) When the graph G is limited to a complete m-partite graph, we give an optimal algorithm with running time O(nlogn).(4) When the graph G is limited to a tree with diameter no more than 4, we give an optimal algorithm with running time O(nlogn).Then, we consider the single machine parallel batch scheduling with an availability constraint. Most literature in scheduling assumes that machines are available at all times. However this availability assumption may not be true in practice. For example, a machine may not be available in the scheduling period due to preventive maintenance or a sudden breakdown. We assume that the unavailable time is known in advance. Two cases are considered: One is called resumable(r-a), provided that if a batch cannot be finished before the unavailable period of a machine, then it can continue after the machine becomes available again. The other is called nonresumable (nr-a) if the batch has to restart rather than continue. It is following the notation of [10]. In the off-line case, we give either a polynomial algorithm or an approximation algorithm. In the on-line case, we give a proof that the lower bound of competitive ratio can be arbitrarily large and also give an optimal on-line algorithm in a special case.Finally, we discuss an on-line model: on-line scheduling with master jobs on a single batching machine. Here, all jobs are on-line. There are some special jobs, of which each has to schedule in a single batch respectively and must be processed once it comes. We call them master jobs, others free jobs. Denote this model by 1|master job; p-batch, b; on-line, r_j|C_max. We consider two cases: the batch meeting with a master job can continue and must restart.The main conclusions are as follows:(5) For the model 1|master job(restart); p-batch, b =∞; on-line, r_j|C_max, we give a best possible on-line algorithm with competitive ratio 2.(6) For the model 1|master job(restart);p-batch, b < n; on-line, r_j|C_max, we give a best possible on-line algorithm with competitive ratio 2.