The Single Machine Parallel-batching Scheduling Problem With Equal Processing Time

Scheduling is to assign jobs processed on machines under some constrains, such that one-or multi-criteria attain to the optimum. The theory of scheduling is an important branch of the operations research, which has received much attention by many scholars. In this paper, we consider the single machine parallel-batching scheduling problem with equal processing time. Our study include: (1) Scheduling a parallel-batching machine subject to precedence constraints,k distinct release dates and equal processing time; (2) Single machine parallel-batching scheduling problem to minimize total weighted tardiness with k distinct release dates and equal processing time.A batch machine or batch processing machine is a machine that can process several jobs simultaneously as a batch, and the processing time of a batch is equal to the longest processing time of all the jobs in the batch. Once the processing of batch is initiated, it cannot be interrupted, nor can other jobs be introduced into the batch.The problems that we study in this paper can be formulated as the following model: Let n jobs J₁; J₂,..., J_n and a single machine that can handle batch jobs at the same time be given. There are precedence relation (?) between the jobs. Each job J_j has a processing time p_j and a release date r_j (where p_j and r_j are integer). The jobs are processed in batches, where a batch is a subset of jobs and we require that the batches form a partition of the set of all jobs. The processing time of a batch is equal to the longest processing time of all the jobs in the batch, i.e., p_x = max{p_j : J_j∈B_x}, x∈{1,2,..., N}. If J_i and J_j are two jobs such that J_i (?) J_j, we also require that Jj be processed after the completion time of J_i; so J_i and J_j cannot be processed in the same batch. The completion time of all the jobs in a batch is defined as the completion time of the batch, i.e., C_x = s_x + max{p_j : J_j∈B_x}.Following [1],[2], we call this modle the parallel-batching scheduling problem and denote it by1|prec;p-batch; r_j|f,where f is the objective function to be minimized. The main conclusion as follow:(1) Scheduling a parallel-batching machine subject to precedence constraints, k distinct release dates and equal processing time.We consider the problem 1|prec: p-batch ;p_i—p;r_i,i∈{1,2,..., k}|L_max. First, we give the definition of block for the parallel batch scheduling with k distinct release dates r_i (1≤i≤k). and show that an optimal scheduleÏ€is given by the release date sequence for each construction of block. Second, we enumerate all construction of block, and give an O(2^k n logkn²) polynomial time algorithm. Finally, we also show that the problem l\prec; p-batch : can be solved in O(2^kn) time.(2) Single machine parallel-batching scheduling problem to minimize total weighted tardiness with k distinct release dates and equal processing time.Baptiste has given an O(n⁸) time dynamic porgramming algorithm in [5] for the problem 1|p-batch ,b < n,r_i,p_i = p|f, , and pointed out that for the criteria batching identical jobs is still an open problem.In this paper, we study the parallel-batching scheduling problem l\prec; p-batch , b < n,r_i,p_i,＝p|∑w_i T_i. First, we suppose the weight of jobs are inversely agreeable with due date of jobs, i.e., w₁≥w₂≥…≥w_n implies d₁≤d₂ < ...≤d_n, and we modified the criteria by a suitable method to become an " ordered objective function ". In this way, the scheduling problem has the special dominance properties. Second, we give dynamic programming parameters and equation, and present an O(b²n⁷)(b < n) time dynamic programming algorithm.