Computer Science ›› 2020, Vol. 47 ›› Issue (6A): 108-113.doi: 10.11896/JsJkx.190300151

• Artificial Intelligence • Previous Articles     Next Articles

Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem

CHEN Meng-hui, CAO Qian-feng and LAN Yan-qi   

  1. School of Software,Nanchang University,Nanchang 330047,China
  • Published:2020-07-07
  • About author:BEN D M, AL F M.A tabu search approach for the flow shop scheduling problem.European Journal of Operational Research, 1998, 109(1):88-95.
    CHEN Meng-hui, born in 1981, Ph.D, associate professor.His main research interests include machine learning and combinatorial optimization.
  • Supported by:
    This work was supported by the MaJor Program of the National Natural Science Foundation of China(11290141),National Natural Science Foundation of China(11401017,11671025) and Fundamental Research of Civil Aircraft(MJ-F-2012-04).

Abstract: Combinatorial optimization is widely used in task problems,such as traveling salesman problem (TSP),scheduling problems.In this study,an evolutionary-based block model (EBBM) was proposed to enhance the speed of convergence so as to avoid premature convergenceproblem.The main idea of blocks is to find key blocks from chromosomes and use these blocks to improve evolutionary algorithms (EAs) to solve combinatorial optimization problems (COPs).Block is a kind of information that explores the effects of individual genes on the evolution of chromosomes,containing information that is helpful for evolution and information that hinders evolution.In this paper,these two different kinds of information are stored and used.The evolution direction of the information providing algorithm,through the influence of two different information,not only improves the convergence speed of the algorithm,but also improves the diversity of the algorithm solution,so as to achieve goals of high stability and good solution quality.The block mechanism proposed includs building a probability matrix,generating blocks by associated rule and applying blocks to construct artificial chromosomes.Since the block is used as the basic unit for constructing the artificial solution in this paper,the blocks mined by the association rules not only have diversity,but also control the block information strength required for the evolution process according to the set confidence level.Finally,in order to confirm the quality of solutions,the proposed approach is experimentally implemented on permutation flow-shop scheduling problem (PFSP).According to the average error rate,the optimal error rate and the convergence curve,the solution effect of the algorithm is discussed,the experimental results show that the block mechanism by positive and negative information is useful to improve the speed of convergence and avoid premature convergence problem.In additional,the results also demonstrate that BBEM is applicable and efficient to the COPs.

Key words: Artificial chromosome, Association rule, Block mining and restructuring, Evolutionary algorithm, Permutation flow-shop scheduling problem

CLC Number: 

  • TP301.6
[1] GAREY M R,GRAHAM R L,JOHNSON D S.Some np-complete geometric problems//Proceedings of the 8th Annual ACM Symposium on Theory of Computing.New York:ACM,1976:10-22.
[2] CHAN F T S,CHUNG S H,CHAN P L Y.Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems.International Journal of Production Research,2006,44(3):523-543.
[3] DORIGO M,MANIEZZO V,COLORNI A.The ant system:optimization by a colony of cooperating agents.IEEE Transactions on Systems,Man & Cybernetics,Part B:Cybernetics,1996,26(1):1-13.
[4] DASGUPTA D,JI Z,GONZLEZ F A.Artificial immune system research in the last five years//IEEE Congress on Evolutionary Computation.New York:IEEE,2003:123-130.
[5] BUDINICH M.A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing.Neural Computing,1996,8(2):416-424.
[6] LIU G Y,HE Y,FANG Y,et al.A novel adaptive search strategy of intensification and diversification in tabu search//Neural Networks and Signal Processing.New York:IEEE,2003:428-431.
[7] WALL M B.A genetic algorithm for resource-constrained scheduling.Cambridge:Massachusetts Institute of Technolo-gy,1996.
[8] HAO X,LIN L,GEN M,et al.Effective estimation of distribution algorithm for stochastic Job shop scheduling problem.Procedia Computer Science,2013,20:102-107.
[9] SANGKAVICHITR C,PRABHAS C.Fragment as a small evidence of the building blocks existence.Berlin:Exploitation of Linkage Learning in Evolutionary Algorithms,2010:25-44.
[10] CHEN M H,CHANG P C,TIWARI A,et al.Bi-variance estimation of distribution model to generate block.Paris World Academy of Science,Engineering & Technology.2013:77.
[11] RUIZ R,MAROTO C,ALCARAZ J.Two newrobust genetic algorithms for the flow shop scheduling problem.Omega,2006,34(5):461-476.
[12] CHANG P C,CHEN S S,FAN C Y.Mining gene structures to inJect artificial chromosomes for genetic algorithm in single machine scheduling problems.Applied Soft Computing,2008,8(1):767-777.
[13] CHEN Y M,CHEN M C,CHANG P C,et al.Extended artificial chromosome genetic algorithm for permutation flow shopschedu-ling problems.Computers & Industrial Engineering,2012,62(2):536-545.
[14] PELIKAN M.Bayesian optimization algorithm.Berlin: Springer,2005:31-48.
[15] CHANG P C,WANG Y W,LIU C H.New operators for faster convergence and better solution quality in modified genetic algorithm//Advances in Natural Computation.Springer Berlin Heidelberg.Berlin:Springer,2005:983-991.
[16] CHANG P C,HUANG W H,WU J L,et al.A block mining and re-combination enhanced genetic algorithm for the permutation flow shop scheduling problem.International Journal of Production Economics,2013,141(1):45-55.
[17] BALUJA S.Population-based incremental learning:a method for integrating genetic search based function optimization and competitive learning.Computer Sciences & Machine Learning,1994.
[18] CHANG P C,CHEN M H,TIWARI M K,et al.A block-based evolutionary algorithm for flow-shop scheduling problem.Applied Soft Computing,2013,13(12):4536-4547.
[19] TAN P N,STEINBACH M,KUMAR V.Introduction to data mining.Addison Wesley,2006.
[20] AGRAWAL R,MIELISKIT,SWAMI A.Mining association rules between sets of items in large databases//ACM SIGMOD Record.New York:ACM,1993:207-216.
[21] MCNICHOLAS P D,MURPHY T B,O’REGAN M.Standardi-sing the lift of an association rule.Computational Statistics &Data Analysis,2008,52(10):4712-4721.
[22] REZA HEJAZI S,SAGHAFIAN S.Flow shop-scheduling prob lems with makespan criterion:a review.International Journal of Production Research,2005,43(14):2895-2929.
[23] REEVES C R.A genetic algorithm for flow shop sequencing .Computers & Operations Research,1995,22(1):5-13.
[24] LIAN Z,GU X,JIAO B.A similar particle swarm optimization algorithm for permutation flow shop scheduling to minimize makespan.Applied Mathematics & Computation,2006,175(1):773-785.
[25] SKELLAM J G.Studies in statistical ecology.Spatial Pattern,Biometrika,1952,39(3/4):346-362.
[26] MILLER B L,GOLDBERG D E.Genetic algorithms,tournament selection,and the effects of noise.Complex Systems,1995,9(3):193-212.
[27] TAILLARD E.Benchmarks for basic scheduling problems.European Journal of Operational Research,1993,64(2):278-285.
[28] CHANG P C,CHEN M H.A block based estimation of distribution algorithm using bivariate model for scheduling problems.Soft Computing,2014,18(6):1177-1188.
[29] HSU C Y,CHANG P C,CHEN M H.A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem.Computers & Industrial Engineering,2015,83:159-171.
[1] CAO Yang-chen, ZHU Guo-sheng, SUN Wen-he, WU Shan-chao. Study on Key Technologies of Unknown Network Attack Identification [J]. Computer Science, 2022, 49(6A): 581-587.
[2] SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance [J]. Computer Science, 2022, 49(6): 297-304.
[3] XU Hui-hui, YAN Hua. Relative Risk Degree Based Risk Factor Analysis Algorithm for Congenital Heart Disease in Children [J]. Computer Science, 2021, 48(6): 210-214.
[4] LI Li, LI Guang-peng, CHANG Liang, GU Tian-long. Survey of Constrained Evolutionary Algorithms and Their Applications [J]. Computer Science, 2021, 48(4): 1-13.
[5] SHEN Xia-jiong, YANG Ji-yong, ZHANG Lei. Attribute Exploration Algorithm Based on Unrelated Attribute Set [J]. Computer Science, 2021, 48(4): 54-62.
[6] ZHOU Sheng-yi, ZENG Hong-wei. Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution [J]. Computer Science, 2021, 48(12): 107-116.
[7] ZHAO Yang, NI Zhi-wei, ZHU Xu-hui, LIU Hao, RAN Jia-min. Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform [J]. Computer Science, 2021, 48(11A): 30-38.
[8] ZHU Han-qing, MA Wu-bin, ZHOU Hao-hao, WU Ya-hui, HUANG Hong-bin. Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms [J]. Computer Science, 2021, 48(10): 343-350.
[9] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[10] ZHANG Su-mei and ZHANG Bo-tao. Evaluation Model Construction Method Based on Quantum Dissipative Particle Swarm Optimization [J]. Computer Science, 2020, 47(6A): 84-88.
[11] CUI Wei, JIA Xiao-lin, FAN Shuai-shuai and ZHU Xiao-yan. New Associative Classification Algorithm for Imbalanced Data [J]. Computer Science, 2020, 47(6A): 488-493.
[12] WANG Qing-song, JIANG Fu-shan, LI Fei. Multi-label Learning Algorithm Based on Association Rules in Big Data Environment [J]. Computer Science, 2020, 47(5): 90-95.
[13] ZHU An-qing, LI Shuai, TANG Xiao-dong. Parallel FP_growth Association Rules Mining Method on Spark Platform [J]. Computer Science, 2020, 47(12): 139-143.
[14] HAN Cheng-cheng, LIN Qiang, MAN Zheng-xing, CAO Yong-chun, WANG Hai-jun, WANG Wei-lan. Mining Nuclear Medicine Diagnosis Text for Correlation Extraction Between Lesions and Their Representations [J]. Computer Science, 2020, 47(11A): 524-530.
[15] YANG Hao, CHEN HONG-mei. Mixed-sampling Method for Imbalanced Data Based on Quantum Evolutionary Algorithm [J]. Computer Science, 2020, 47(11): 88-94.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!