Research On Algorithms Of Some Batch Scheduling Problems

In the last decade, there has been significant interest in single machine scheduling problems that involve batching. We consider the problem of scheduling on a single paral-lel batching machine. We are given a set of n jobs and a single parallel batching machine with capacity B. Each job Jj(j∈{1,2,..., n}) is characterized by a tuple of integer num-bers (rj, pj, size j, wj), where rj is the release date before which job Jj cannot be sched-uled; pj is the processing time which specifies the minimum time needed to process job Jj without interruption; sizej is the size of job Jj, and wj is the penalty paid to job Jj if it is rejected. The machine can process a number of jobs simultaneously as a batch as long as the total size of the jobs in the batch does not exceed B. The processing time of a batch is the longest processing time of any job in the batch. Jobs processed in the same batch have the same start time and the same completion time. Our goal is to schedule the jobs so that the makespan of the accepted jobs plus the total penalty of the rejected jobs is minimized.First, we show that the problems are NP-hard and the worst-case ratios of them are at least 3/2; then, we propose a 2-approximation algorithm for the special case with identical release dates; finally, we present an approximation algorithm for the general problem with worst-case ratio 2+∈, where∈> 0 is an arbitrarily small constant.Motivated by the real-time machine-vision systems, we also consider parallel batch-ing scheduling problem to minimize makespan in hybrid flow-shop environments using genetic algorithms. The problem can be stated as follows:Consider a set J of n jobs to be processed in a k-stage flow-shop, where each stage i has mi parallel batching processors, i∈{1,2,..., k}. Let Bip denote the capacity of processor p of stag i, i∈{1,2,..., k), p∈{1,2,..., mi}. That is, processor p of stage i can process at most Bip jobs simultane-ously. The processing time of a batch is equal to the largest processing time among its members. It is convenient to view a job as a sequence of k tasks-one task for each stage, where the processing of any task can commence only after the completion of the preceding task. Let pij be the time needed to process j ob Jj at stage i, i∈{1,2,..., k}and Jj∈J. We have the following assumptions for the problem:1. Processors used at each stage cannot process tasks corresponding to any other stages; 2. During the processing of a batch, no new batch can start on the same processor. Let Cij(S) be the completion time of the ith task of job Jj in schedule S, i∈{1,2,..., k} and Jj∈J. We consider the makespan minimization problem, i.e., to find a schedule S that minimizes max.Jj∈J{Ckj(S)}. We give two methods for crossover and mutation separately and implement four versions of the genetic algorithm, one for each combination of the crossover and mutation operators to investigate the performance. Then, we focus on the single batching machine scheduling problem with job sizes and rejection to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs, and give a new decoded method and four versions of genetic algorithms. Experiments show that one of the algorithms peferms better than others.