Research On Hybrid Flow Shop Load Balancing Scheduling Optimization Problem

Hybrid flow shop is a combination of classic flow shop and parallel machine shop, which widely exists in many key sectors of national economy like automobile production, semiconductor packaging, large equipment manufacturing and so on. HFS possesses the characters of multi-task, multi-stage and multi-machine. In the process of machining, different tasks have different process routes, one task may have different processing time when processed on different parallel machine, which means the productive capacity of parallel machine may be different. Hybrid flow shop production scheduling is an integral of parallel machine allocation and job sorting, those characters make HFS scheduling problem more complex than the ordinary flow shop problem, and it is a typical NP-hard problem. Workshop load balancing is aim to use a feasible method to control the parallel machine selection to make the total number of jobs allocted on each parallel machine same or similar when to process a task set, which can avoid parallel machine overloaded or idle, and then improve the production efficiency of HFS. With the popularity of multi-item and small batch production mode, in hybrid flow shop, the diversity of jobs in a task is incrased, data information amont of scheduling load is large and hard to count, which make the load balancing control more difficult, moreove, there not exist a complete evaluate index system for load balancing scheduling optimization prolem yet. Therefore, research on HFS load balancing scheduling problem(Hybrid flow shop- the load balancing scheduling problem, HFS-LBSP) has a great theoretical significance and practical application value.In this paper, HFS load balancing scheduling problem is studied, based on the analysis of the dynamic production rule of workshop and the discrete control system' modeling theory, a mathematical model of hybrid flow shop was formulated, amd then a deeply study of HFS-LBSP is conducted from the global optimization methods, evaluation indexs and re-entrant stages' constraint aspects. In the aspect of global optimization methods, with the increasingly outstanding of the superiority of swarm intelligence algorithm, the using area is more widely, select a population method to solve the HFS-LBSP is reasonable. Therefore, in this paper, the differential evolution algorithm and the improved algorithm are selected to complete the global optimization, because it is easily to conduction, has fewer parameters and good optimization quality. And then, it is sure that the main optimization objective is the parallel load balancing problem, but for workshop production system, production efficiency is the basic but most important require that need to meet first, therefor, when designing the load balancing evaluation indexs system, take the weighted summation of the processing time load balancing cost and the total parallel machine waiting time is set as load balancing comprehensive evaluation index. At last, there may exist these jobs which need to be processed on one stages more than one times, in other words, there exist re-entrant stages in hybrid flow shop production processing, which would make it more difficult to balance the load of parallel machine. Hence, the re-entrant hybrid flow shop load balancing scheduling problem is another part of this study.The main content of the research: firstly, a mathematical model is formulated for HFS load balancing scheduling problem, which including the objects of stages, parallel machines, jobs, process procesures and the relationship and constraint of those object. Besides, study of swarm intelligence algorithm, including the classical GA algorithm, the new cuckoo search algorithm, and the DE algorithm; a simulation is conducted through actual HFS workshop data based on makespan optimization problem to verify the superiority of DE algorithm; Then, a deeply study on DE algorithm is conducted, and two improved DE algorithms are proposed: double population self-adaptive differential evolution algorithm and dynamic self- adaptive differential evolution algorithm, and verify their optimal performance. Secondly, aimed to solve the hybrid flow shop load balancing scheduling optimization problem, based on the analysis of the factors which would influencing the load balancing, a hybrid flow shop load balancing production scheduling optimization problem' evaluation index system construct in which the weighted summation of the processing time load balancing cost and the total parallel machine waiting time is set as load balancing comprehensive evaluation index, and the DPSADE algorithm is used for the global optimization purpose, two different scale datas from actual workshop were simulated, Through comparison with GA, DE and SADE algorithm, the results show that the rate of decrease for load balance evaluation index is nearly 30%. Secondly, considering if exists re-entrant process constraints during the process of hybrid flow shop production scheduling, the real-time state's statistics of the job and location are harder in its production process, the uncertainties in workshop would increased, and the load balancing control would be more difficult. Therefore, In-depth research on the re-entrant hybrid flow shop load balancing problem, a new encoding method based on job processing procedure was designed, coupled with time-window constraint and the largest remaining time rules to finish the decoding process, and also cooperated with DSADE algorithm to complete the global optimization. An example of production scheduling problem for multi-pass color strip procedure in bus manufacturing painting workshop was simulated. Through comparison with GA, DE and SADE algorithm, the results show that the rate of decrease for load balance evaluation index is more than 20%.