Study On Self-adaptive Differential Evolution Solving Multi-objective Flow Shop Scheduling Problem With Limited Buffers

Flow shop scheduling problem(FSSP) is a significant branch of combinatorial optimization problems. Researching on FSSP facilitates optimal allocation and rational utilization of the limited resources. But this problem is non-deterministic polynomial hard(NP-hard). Now artificial intelligence approaches are being used instead of traditional mathematical methods and have acquired some achievements.FSSP has many categories. FSSP with limited buffers(FSSPWLB) is gaining extensive attention due to the fact that it is closer to the actual production status.Discussing the size of buffers also has important economic value in practical production. In addition, solving multi-objective FSSPWLB helps decision maker formulate compromise strategies so that the benefit maximization and other production targets are realized on the premise of satisfying the needs of clients. So,study on multi-objective FSSPWLB is of great importance.Differential evolution(DE) has been increasingly applied to continuous optimization problems because of its nice property. Parameters of DE are sensitive to problems optimized. Generally, the setting of proper values is based on a great amount of experimental results or experience which results in extra computation and is constrained by prior experience simultaneously. As a result, self-adaptive DEs emerge in large numbers continually and its application area is being broadened.Considering tested instances come in different size, the participation of self-adaptive mechanism is needed more when DE is used to optimize FSSPWLB.To sum up, a self-adaptive DE and several variants were proposed in this task to solve multi-objective FSSPWLB. So far, it is the first time that a self-adaptive DE is applied to handle multi-objective FSSPWLB.Firstly, largest order value(LOV) rule was employed to accomplish the mapping between DE individuals and job permutations here. In order to design reasonable self-adaptive mechanism, the relationship among the differences of DE individuals,job permutations and target values was analyzed to throw light on the likely effect of CR and F on target values. Based on what was done above, a self-adaptive DEabout parameter CR was presented to adapt different search requirements.Meanwhile to guarantee the quality of the initial population, two special individuals were constructed through two heuristic approaches.Next, to strengthen the local search performance, a local search based on probability model(LSbPM) was presented apart from insert operator(Insert) to excavate high-quality subsequences from non-dominated solution set and put them to use. Inferior solution retention mechanism was introduced to retain potential solutions in the repeatedly searching process to make the best of search results and compensate useless computation from discarding dominated solutions directly to some extent.Then to verify the proposed algorithm in the thesis, other two variants were designed and HDE from another literature was tested as a comparison. LSbPM operator was excluded from the first one and inferior solution retention mechanism was removed from the second one. The three algorithms were recorded as MPADE1,MPADE2 and MPADE3. 12 instances from three benchmarks were selected as test data. These three algorithms were compared with each other and HDE via experiment results measured by several assessment criteria. Results show that inferior solution retention mechanism plays a key role in the MPADEs which allows MPADE1 and MPADE3 to outperform MPADE2 and HDE. While the function of LSbPM is not ideal as this local search operator works only with more evaluation. On the whole,MPADE3 is the beat one because the algorithm btains more non-dominated solutions,guarantees the quality of the solutions at the same time. In addition, the distributivity of solutions MPADE3 gets is better than those of other algorithms.Last, MPADE3 was used to test the convergence behavior compared with HDE and analyse the effect of different buffer size on FSSPWLB. Results demonstrate that a faster convergence speed is observed by MPADE3. A better distributivity is reflected again. Buffer matters in the actual production process. The improvement from the optimized functions is not in proportion to the increase of buffers. This conclusion can be utilized to direct machine configuration.