Research Into Algorithm Design And Application Of Non-exclusive Flow Shop Scheduling Problem

With the advances of scientific technologies, production becomes increasingly large-scale and complex, and market competition is more and more fierce, which pose higher demands on the business administration and supervision of the production processes. Faced with tough competition, the original simple, local and conventional control and experience-based management can no longer meet the demands of modern production. How to make full use of the existing advantages in resources and to yield profits in a highly efficient and reasonable way is an important problem facing the managers of modern enterprises. Scheduling problem is just one type of the problems manufacturing enterprises have to deal with and a key problem of production management. The purpose of scheduling is to optimize working procedures, so as to improve the production efficiency and reduce the costs for the manufacturing enterprise.Classic scheduling theories had already taken shape in 1950s; however, the conclusions already achieved are not sufficient yet for many specific production conditions, considering the complexity of the practical working methods. Meanwhile, the algorithm studied in the thesis is to solve the scheduling problem in a large-scale state-owned military enterprise which boasts solid technologic strengths and high-rate facilities. After reform, it became involved in civil manufacturing and began to provide spare parts for many manufacturers of airplanes. Having long been influenced by the planned economy, the decisions for the enterprise are largely based on experiences and the shop scheduling is quite rough and careless. The scheduling problem that appears in the production process of the enterprise has so far not been solved despite its frequency attendance in the practical situation, and we call it non-exclusive scheduling. The so-called non-exclusive Flow shop scheduling problem refers to those with non-exclusive equipment which can process more than one component at the same time. The non-exclusive equipment have made the scheduling problem even more complicated and has a much bigger space of feasible solutions. To solve the problem, it's essential to find an algorithm which has good performance on either efficiency or effectiveness.This thesis researches into a non-exclusive Flow shop scheduling problem which frequently occurs in real production processes but receives relatively less attention from academic studies.This thesis starts with algorithm analysis of the Flow shop scheduling problem, choosing GA which is universally applicable as the main algorithm of the problem, and builds up the algorithm framework according to steps of the basic GA. Then, in line with the "prematurely" and low efficiency of the basic GA, methods of division of population and combination of Tabu Search (TS) are introduced. Next, after analyzing, two tactics based on RD coefficient (ROD) and Reservation of best (ROB) are proposed for further improvement and a hybrid GA on the basis of population division is designed. The rationality and effectiveness are proved by comparison between pragmatic study and basic GA.Using the simulation data provided by the enterprise, the algorithm presented by this thesis works quite well, which means that non-exclusive flow shop scheduling problem of the enterprise is expected to be solved and thus the productivity will be further improved.