Research On Algorithms For Scheduling Parallel Batch Processing Machines With Non-identical Job Sizes

Batch scheduling,as a new type of scheduling problem,has drawn the attention of scholars in recent decades.It has been widely applied in many research areas such as electronics manufacturing facilities,transportation and metal working.Unlike classical machines,a batch processing machine can process multi-jobs simultaneously,which can promote the production ability of enterprises greatly.Reasonable scheduling can achieve effective supervision and control of the production process,thereby enhancing the competitiveness of enterprises.Consequently,research on batch scheduling prob-lems,and improving the utilization of resource by optimizing scheduling can have the great theoretical value and practical significance for the increase of enterprise produc-tion management.This paper considers parallel batch processing machines problems with non-identical job sizes.Since the problems considered are NP-Hard,some intelligent optimization algorithms are proposed.The main research contents and innovations are as the follow-ing:(1)The problem of parallel batch processing machines with non-identical job sizes is considered.The objective is to minimise makespan.First,a mixed integer program-ming model is formulated for this problem,and a lower bound is presented to evaluate the quality of solutions.Then a MFF-LPT heuristic is developed to form and schedule batches.Besides,an estimation of distribution algorithm based on probability matrix with 4 different update mechanism is developed to solve this problem.Computation experiments are conducted and comparisons with genetic algorithm and simulated an-nealing algorithm demonstrate the effectiveness of the proposed algorithm.(2)The scheduling problem of non-identical parallel batch processing machines with dynamic job arrivals and arbitrary job sizes is examined.The objective is to min-imise makespan.First,a mixed integer programming model is summarized.Then an artificial bee colony algorithm based on job permutation encoding is proposed.In this algorithm,we develop a new heuristic to form and schedule batches simultaneously.To improve the quality of solutions,a local optimization algorithm is embed in the pro-posed algorithm.And experiments of random instances are conducted to evaluate the performance of proposed algorithm by comparison with some existing algorithms.Finally,all works of this dissertation are summarized,and future research related to batch scheduling are given.