Research On Flow Shop Scheduling Problem Based On Improved SFLA And AGA

Production scheduling plays a key role in Computer Integrated Manufacturing System. It is not only responsible for the upper layer of enterprise decision-making, but also responsible for the lower layer of monitor controlling to ensure the normal operation of the production. Production scheduling also infects the cost control and benefit maximization of the company and has a great influence of Globalization, Information and Integration of Chinese Manufacturing Industry. Flow shop is an important scheduling problem. This paper investigated the complicated scheduling problem through designing and improving several intelligent optimization algorithms. Experiments demonstrated the effectiveness of the proposed algorithms.A new meta-heuristics named shuffled frog leaping algorithm (SFLA) is proposed for the permutation flow shop scheduling problem (PFSP) with makespan objective. SFLA is rather effective for the confusion of shuffled complex evolution (SCE) and discrete particle swarm optimization. A new leaping rule is presented to improve SFLA and experiments showed the effectiveness of proposed methods.For the PFSP with uncertain processing time, a new shuffled frog leap algorithm (NSFLA) was presented. To solve the problem that the local search of SFLA is easy to generate illegal solutions, two tracking strategies, "Randomization of the initial position in swap sequence constructing" and "Random inserting of the swap operator", was proposed based on the concept of the swap operator and swap sequence. Computational results show the effectiveness of the NSFLA comparing with the standard GA.PFSP with total flow time criterion is considered. An asynchronous genetic local search algorithm (AGA) is proposed to deal with this problem. AGA consists of three phases. In the first phase, an individual in the initial population is yielded by an effective constructive heuristic and the others are randomly generated, while in the second phase all pairs of individuals perform an asynchronous evolution (AE) procedure by using an enhanced variable neighborhood search (E-VNS) strategy as well as a simple crossover operator. A restart mechanism is applied in the last phase. Experimental results show that the algorithm proposed outperforms several state-of-the-art methods and two recently proposed meta-heuristics in both solution quality and computation time. Moreover, for 90 benchmark instances, AGA obtains 89 best solutions reported in the literature and 54 of which are newly improved.