Applying Sequential Pattern Mining to Generate Block for Scheduling Problems

Authors: Meng-Hui Chen, Chen-Yu Kao, Chia-Yu Hsu, Pei-Chann Chang

Abstract:

The main idea in this paper is using sequential pattern mining to find the information which is helpful for finding high performance solutions. By combining this information, it is defined as blocks. Using the blocks to generate artificial chromosomes (ACs) could improve the structure of solutions. Estimation of Distribution Algorithms (EDAs) is adapted to solve the combinatorial problems. Nevertheless many of these approaches are advantageous for this application, but only some of them are used to enhance the efficiency of application. Generating ACs uses patterns and EDAs could increase the diversity. According to the experimental result, the algorithm which we proposed has a better performance to solve the permutation flow-shop problems.

Keywords: Combinatorial problems, Sequential Pattern Mining, Estimation of Distribution Algorithms, Artificial Chromosomes.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1092589

References:

[1] R.Agrawal, T.Imielinski and A.Swami, 1993. MiningAssociation Rules between Sets of Items in Large Databases.In Proc. of the 1993 ACM-SIGMOD Conf. on Management ofData, 207-216.
[2] Agrawal, R. and Srikant, R. 1995. Mining Sequential Patterns, In Proc. of the 11th Int’l Conf. on Data Engineering, 3-14.
[3] J. T. Tsai, W. H. Ho, T. K. Liu, and J. H. Chou, "Improved immune algorithm for global numerical optimization and job-shop scheduling problems,” Applied Mathematics and Computation, Vol. 194, pp. 406-424, Dec. 2007.
[4] J. S. Chun, H. K. Jung and S. Y. Hahn, "A Study on Comparison of Optimization Performances between Immune Algorithm and other Heuristic Algorithms,” IEEE Transactions on Magnetics, vol. 34, No. 5, Sept. 1998.
[5] J. H. Holland, "Genetic Algorithms and the Optimal Allocation of Trials,” SIAM J. Comput, vol. 2, pp. 88-105, 1973.
[6] D. E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning (Book style),” Boston, MA: Addison-Wesley, 1989.
[7] P. C. Chang, S. H. Chen, & Fan, C. Y. (2008). "Mining gene structures to inject artificial chromosomes forgenetic algorithm in single machine scheduling problems,” Applied Soft Computing Journal, 8(1), 767–777.
[8] Fardin Ahmadizar, "A new ant colony algorithm for makespan minimization in permutationflowshops,”Applied Computers & Industrial Engineering, Vol. 63, pp.355-361, 2012.
[9] W. E. Costa, M. C. Goldbarg, E. G. Goldbarg, "New VNS heuristic for total flowtimeflowshop scheduling problem,”Applied Expert Systems with Applications, Vol. 39, pp.8149-8161, 2012.
[10] Q. K. Pen, R. Ruiz, "Local search methods for the flowshop scheduling problem with flowtimeminimization,”Applied European Journal of Operational Research, Vol. 222, pp.31-43, 2012.
[11] X. Dong, P. Chen, H. K. Huang, &Maciek Nowak, "A multi-restart iterated local search algorithm for the permutation flowshopproblem minimizing total flowtime,”Applied Computers & Operations Research, Vol. 40, pp.627-632, 2013.
[12] M. F.Tasgetiren, Q. K. Pan, P. N. Suganthan, A. H. Chen, "A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops,”Applied Information Sciences, Vol. 181, pp.3459-3475, 2011.
[13] C. Sangkavichit,P.Chongstitvatana, "Fragment as a Small Evidence of the Building Blocks Existence,” Applied Evolutionary Learning and Optimization, Vol. 3, pp.25-44, 2010.
[14] Pei-Chann Chang, Meng-Hui Chen, Manoj K. Tiwari, AsifSikandarIquebal: A block-based evolutionary algorithm for flow-shop scheduling problem. Appl. Soft Comput. 13(12): 4536-4547 (2013).
[15] Chang, Pei-Chann, and Meng-Hui Chen. "A block based estimation of distribution algorithm using bivariate model for scheduling problems." Soft Computing (2013): 1-12.
[16] R.Agrawal, T.Imielinski and A. N.Swami,1993. Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, P. Buneman and S. Jajodia, Eds. Washington, D.C., 207-216.
[17] Q. Zhao and S. S. Bhowmick, "Sequential pattern mining: a survey,” Technical Report, CAIS, Nanyang Technological University, Singapore, No.2003118, 2003.
[18] Y. M. Chen, M.C. Chen, P. C. Chang, and S. H. Chen, "Extended artificial chromosome genetic algorithm for permutation flowshop scheduling problems,” Computers & Industrial Engineering, Vol. 62, pp.536-545, 2012.
[19] ShigeyoshiTsutsui, "Probabilistic Model-Building Genetic Algorithms in Permutation Representation Domain Using Edge Histogram,” Lecture Notes in Computer Science Volume 2439, pp.224-233, 2002.
[20] Chen, S. H. & Chen, M. C., "Addressing the advantage of using ensemble probabilistic models in Estimation of Distribution Algorithms for scheduling problems,” Int. J. Production Economics, Vol. 141, pp. 24-33, 2013.