Research On Heuristics For Scheduling Non-identical Jobs On Batch Processing Machines With Different Capacities

The production scheduling problem is a combinatorial optimization problem has a broad background, and it has now been applied to many fields, such as logistics, manufacturing, network communication and so on. It refers to in a certain period of time allocation of the shared resources by the right sort, and in order to achieve one or several target, we will have the rational planning and distribution for each task in the process of production, and the reasonable scheduling scheme can improve the utilization rate of resources and the production efficiency largely, and reduce the production costs, thus will increase the competitiveness of the enterprise, also can promote the development of the society.Batch scheduling is an important extension of the traditional classical scheduling problems, because of its more comprehensive theoretical background and application value in the real life, so it has become a hotspot of the current production scheduling problems. In the batch scheduling problem, it allows several jobs on a single machine for processing at the same time; in the batch scheduling problem with non-identical job sizes, it is to explore the scheduling problem that the jobs whose processing time and size are different will be processed on the machine; the dynamic context processing refers to that the jobs which have the different arrive times will consider the start time of the process. The scheduling is often closer to the real production environment, but also because of its features, such as many kinds of goal functions, a variety of constraints, uncertainties and so on, so many batch scheduling problems have not been more secure solution, and has proved that many of these problems are NP-hard problem. So for very complex production environments, how to design a simple and efficient solution algorithm has always been a focus of research on batch scheduling problem.Firstly, this paper introduces the basic concept of production scheduling problems, including the background of scheduling problems, such as the three parameter representation that is commonly used in the world in the scheduling problems and the categorization of scheduling problem. Next, the batch scheduling problem, the batch scheduling problem with non-identical job sizes and the batch scheduling problem with non-identical job sizes in the dynamic environment are introduced. Then from the single machine environment, parallel machines environment and workshop environment, we describes current research status of the batching scheduling problem, and the problems in the current study were discussed briefly. And then the paper introduces the methods for solving scheduling problems in detail, and gives specific examples of various algorithms, such as FFLPT, BFLPT and other classic heuristic algorithm and meta-heuristic algorithms:Ant Colony algorithm, genetic algorithms and simulated annealing and so on.Then, the paper discusses the batch scheduling problems with non-identical job sizes and the different machines in the dynamic environment. In the current research on batch scheduling, the constraints and the processing environment is relatively simple, such as it is little regard for the arrival time of the jobs in processing tasks (they are usually treated as 0), the most of machines have the same capacity in the processing environment and so on, therefore the batch scheduling problem with non-identical job sizes and the different machines in the dynamic environment is put forward and studied. In response to questions, this paper presents several heuristic optimization algorithm based on rules. In the paper, the solution of the problem is divided into two sub-problems:first it uses FFD and BFD heuristic rules to work for batch, means the jobs according to the set of rules are assigned to different batches; then based on the batch of the collection, respectively using FFLPT and BFLPT algorithms for batch scheduling, and the batch is assigned to a machine for processing. And in the batch scheduling process, MultiFit rules for further optimization of the objective function to minimize the production span. Through the simulation experiment, we compare the heuristic algorithm proposed in this paper with the LB algorithm and the performance verification and performance analysis are presented, the experimental results show that the algorithms in this paper is efficaciously for the batch scheduling problem whose capacity of the machines and job sizes are different in the dynamic environment, and the performance of BFD-BFD algorithm is better than several other algorithms.Finally, the research content of this article was summarized, and the future research direction was also discussed.