Some Researches On Flow Shop Scheduling Problems Based On Swarm Intelligence Optimization

Production scheduling problem is a decision-making process that plays a crucial role in manufacturing and service industries and widely exists in practical environments, such as chemical, oil, tobacco, textile, paper, pharmaceutical and food industries. It concerns how to allocate available production resources to tasks over given time periods, aiming at optimizing one or more objectives. At the same time, this problem is categorized as a very typical combinatorial optimization problem, and many kinds of subproblems are NP-hard. When we solve these subproblems, the traditional methods are difficult to obtain satisfactory results, especially for some complex problems, it can not even get feasible solutions. Therefore, the production scheduling problem has great significance in both engineering and theoretical fields, and it is meaningful to develop effective and efficient approaches for this problem. This dissertation analyses four typical flow shop scheduling problems:the blocking flow shop scheduling problem, the flow shop scheduling problem with limited buffers, the hybrid flowshop scheduling problem, and the hybrid flowshop scheduling problem with random breakdown, establishes the corresponding models, and proposes some swarm intelligence optimization algorithms for solving these problems. The main content of this dissertation can be summarized as follows:(1) For the blocking flow shop scheduling problem (BFSP), a discrete group search optimizer (DGSO) algorithm is proposed to minimize the total flow time. In the proposed DGSO algorithm, an efficient population initialization based on the NEH heuristic and NEH-WPT heuristic is incorporated into the random initialization to generate an initial population with certain quality and diversity; moreover, the insert neighborhood search, the discrete differential evolution scheme and the destruction and construction procedures are hybridized to improve the algorithm performance; in addition, an orthogonal experiment design is employed to provide a receipt for turning the adjustable parameters of the DGSO algorithm. The simulation results on benchmarks demonstrate the effectiveness and efficiency of the proposed DGSO algorithm.(2) A hybrid discrete harmony search (HDHS) algorithm is proposed for the flow shop scheduling problem with limited buffers (LBFSP). The HDHS algorithm presents a novel discrete improvisation and a differential evolution scheme with the job-permutation-based representation. Moreover, the discrete harmony search is hybridized with the problem-dependent local search based on insert neighborhood to balance the global exploration and local exploitation. In addition, an orthogonal test is applied to configure the adjustable parameters in the HDHS algorithm. Comparisons based on the Taillard benchmark instances indicate the superiority of the proposed HDHS algorithm in terms of effectiveness and efficiency.(3) The hybrid flowshop scheduling (HFS) problem is modeled by vector representation, and then an improved discrete artificial bee colony (IDABC) algorithm is proposed for this problem to minimize the makespan. The proposed IDABC algorithm combines a novel differential evolution and a modified variable neighborhood search to generate new solutions for the employed and onlooker bees, and the destruction and construction procedures are used to enhance the ability of global search for the scout bees. Moreover, an orthogonal test is applied to efficiently configure the system parameters, after a small number of training trials. The simulation results demonstrate that the proposed IDABC algorithm is effective and efficient comparing with several state-of-the-art algorithms on the same benchmark instances.(4) The production scheduling problems have been discussed in the literature extensively under the assumption that the machines are permanently available without any breakdown. However, in the real manufacturing environments, the machines could be unavailable inevitably for many reasons. Here the authors introduce the hybrid flowshop scheduling problem with random breakdown (RBHFS) together with an improved discrete group search optimizer algorithm (IDGSO). In particular, two different working cases:preempt-resume case and preempt-repeat case are considered under random breakdown. The proposed IDGSO algorithm adopts the vector representation and several discrete operators, such as insert, swap, differential evolution, destruction and construction in the producers, scroungers, and rangers phases. The computational results in both cases indicate that the proposed algorithm significantly improves the performances compared with other high performing algorithms in the literature.