A Probability Model-based Memetic Algorithm for Distributed Heterogeneous Flow-Shop Scheduling

摘要

With the trend of global manufacturing, distributed shop scheduling has been a hot research topic recently. This paper addresses the distributed heterogeneous permutation flow-shop scheduling problem with multiple non-identical factories to minimize makespan. To well solve the problem, a probability model-based memetic algorithm (PMMA) is presented in this paper. Since the non-identical factories have different process capabilities, it is crucial to determine reasonable factory assignment. In PMMA, a probability model is constructed to reflect the probability distribution of factory assignment. At each generation, the probability model is updated by elite individuals to search for good factory assignment scheme. The information from the probability model is extracted and integrated in the designed search operators to help adjusting factory assignment and processing order. Meanwhile, the search operators collaborate to achieve both exploration and exploitation ability. Besides, a local intensification operator is designed to further improve the solution quality. Extensive computational experiments are carried out to test the performance of PMMA. The experiment results demonstrate the effectiveness of the designed PMMA.