Abstract: Permutation flow-shop scheduling problem (PFSP) is different kind of the combinatorial problems and is categorized as NP-Hard problem, which is a very typical production planning problem in the field of shop scheduling. The goal of solving PFSP is devoted to finding out an optimal permutation so that makespan is minimal. To find the solution of PFSP is a common challenge in which an algorithm may be trapped in the local optima of the objective function when the complexity is high, and there are several local optima in solution space. In response to the above issues, this study proposes a biogeography-based optimization based on linkage learning (LLBBO) for solving PFSP with the objective of minimizing the makespan. The main contribution of this study is to propose a novel algorithm that greatly improves the effectiveness and efficiency when compared with previous researches in solving benchmark PFSPs. Moreover, the proposed algorithm is expected to be applied to solving other combinatorial optimization problems.
The algorithm takes biogeography-based optimization as architecture, using opposition-based learning mechanism to generate initial groups. The initial groups are divided into dominant group and disadvantage group according to population fitness, based on which the immigration and emigration rates are calculated and the habitat with high HSI has a higher immigration rate. After that, the information entropy is used to calculate the entropy value of each position of the solution sequence. By describing the degree of clutter of the workpiece on each machine, the key machine with a low degree of clutter can be effectively found out as the location covered by the linkage blocks. The linkage blocks are constructed based on the key locations calculated using information entropy. Linkage blocks are linkage structure units that mine frequently occurring segments at the same location or arrangement in the solution sequence based on the statistical information of the solution sequence of a population. These combination of linkage segments can improve the fitness of the solution sequence. The probability matrix model is used to statistically analyze the solution sequence information and generate an initial linkage fragment containing the key location, which is then combined according to mining rules. Next, we use linkage blocks to simulate the migration operation of BBO algorithms to update the population. Specifically, we select a specified proportion of linkage blocks from the database in a random manner, replace them into a sequence based on the location information of the linkage blocks, and arrange the repetitive jobs in the order that optimizes the objective function value of the solution sequence. In order to further improve the searching ability of the algorithm, a NEH reorganization strategy is proposed to perform the segmentation and reorganization on the solution sequence. Then, the proposed LLBBO uses a random mutation operation to enhance search performance and provide more search targets.
To verify the effectiveness of the proposed scheme, computational simulations are conducted on Reeves's and Taillard's benchmark instances. First, the proposed LLBBO is applied to solve Reeves's instances, and the experimental results are compared with classical algorithms such as BBEDA, HDBBO, and VP-QEA. The results show that the BRE of all instances solved by the LLBBO are the best among the compared algorithms, and the average value of ARE is superior to other compared algorithms except HDBBO. Second, we apply the proposed LLBBO to solve the Taillard's benchmark instances and compare the results with ACGA, BBEDA, LMBBEA, and the convergence graphs of the proposed algorithm on some test instances are given. Compared with other algorithms, the proposed algorithm can achieve better average error rates and minimum error rates on most cases.
This study applies the concept of information entropy to the selection of key locations of linkage blocks. The expansion of information entropy in constructing linkage blocks and the applicability of further development algorithms to other types of combinatorial optimization problems can be studied in the future. Future works can also be extended in applying this method to several other combinatorial problems.

Key words: permutation flow-shop scheduling, information entropy, linkage learning, biogeography-based optimization, NEH heuristic algorithm

摘要： 针对置换流水车间调度问题的特性,提出了一种基于链接学习的生物地理学算法(Biogeography-based optimization based on linkage learning,LLBBO)来对其求解。算法以生物地理学算法为架构,使用反向学习方法(Opposition-based learning,OBL)生成初始解,依据群体适应度值将群体分为优秀群体和劣势群体,使用信息熵的概念以及数理统计方法通过对这两个群体进行统计,分别建立概率矩阵模型以构建一种链接学习模型称为链接区块,使用链接区块依照算法迁移率对群体进行迁移操作实现群体更新。为进一步改善算法的搜寻性,提出一种NEH序列重组法对解序列执行局部搜索以进一步提高适应度。最后运用所提的LLBBO算法通过对基准例题的仿真测试和算法比较验证了所提算法的有效性。

关键词: 置换流水车间调度, 信息熵, 链接学习, 生物地理学算法, NEH算法