Research On Scheduling Batch Processing Machines In Parallel

Problems of scheduling batch processing machines (BPMs) are a new category of optimization problems in the field of scheduling with strong application background. Problems of Scheduling batch processing machines are encountered in various manufacturing and production environments. Different from traditional production scheduling problems in which only one job can be processed on a machine at a time, batch processing machines can process several jobs together as a batch as long as the total size of jobs in the batch does not exceed the machine capacity. As a result, both the problem of arranging jobs into batches and allocating batches to machines should be studied in the problem of scheduling batch processing machines. Scheduling batch processing machines are more complicated than traditional scheduling problems and many of them have been proved to be NP-hard. It makes great sense to study the problems of scheduling batch processing machines.A lot of researches have been done in the field of scheduling batch processing machines. Most of that focus on single or identical parallel batch processing machines. The study should be extended to more general condition with the development of flexible manufacturing.The problem of scheduling identical parallel batch processing machines, uniform parallel batch processing machines and unrelated parallel batch processing machines to minimize Makespan are studied in this paper. The main researches are listed as following:1) The problem of scheduling batch processing machines was extended to the distributed environment. In the problem, jobs had non-identical release times and the transportation times were considered before and after batch processing. The problem was shown to be strongly NP-hard thus a lower bound was presented to evaluate the performance of approximation algorithms. Several heuristics for the problem were proposed based on algorithm AR (Assignment Rule) and BR (Batching Rule). Computational experiments showed the effectiveness of the heuristics was improved especially when the BR was used.2) Batch scheduling problem with non-identical job sizes on uniform parallel machines was proposed and solved. There were m machines in parallel with different speeds. The problem was shown to be NP-hard; thus a lower bound was presented to evaluate the performance of approximation algorithms. The Max-Min ant system (MMAS), improved by a local optimization algorithm LORPT (Local Optimization with Recessive Processing Time) based on the idea of recessive processing time, was applied to group the jobs into batches. A heuristic algorithm MMAS-LPTUM (Longest Processing Time for Uniform Machines) was then used to solve the problem under study. The computational experiment was performed to analyze the heuristic algorithms MMAS-LPTUM, GA, PSO and BFLPT and MMAS-LPTUM outperformed others.3) The problem of scheduling batch processing machines to minimize the Makespan on uniform parallel machines in the presence of dynamic job arrivals was studied. The machines had different speeds and each machines worked at a consistent rate. The problem under study was NP-hard for Makespan objective. Thus, several heuristics were proposed. A Batching Rule BR was given to balance the release times and processing times when heuristics were used to form the batches. After the batches were formed, a heuristic ARUM (Assignment Rule for Uniform parallel Machines) was proved to allocate them to uniform parallel machines. A lower bound was also presented to evaluate the performance of the algorithms via computational experiments. The results showed that the problem could be solved effectively and the heuristic BFLPT (Best Fit Longest Processing Time) improved by BR outperformed other heuristics.4) Scheduling unrelated parallel batch processing machines for minimizing Makespan was studied in this paper. The speeds of machines were independent from jobs. Several heuristics based on BFLPT (best fit longest processing time) in two groups were proposed to solve the problem based on different schedule mechanisms. A lower bound was also proved to evaluate the quality of the heuristics. Computational experiments showed that J_SC-BFLPT was robust and outer performed other heuristics for most of the problem categories.