Lu Lin

A New Maximum Entropy Estimation of Distribution Algorithm to Solve Uncertain Information Job-shop Scheduling Problem

Full Text (PDF, 208KB), PP.1-8

Views: 0 Downloads: 0

Author(s)

Lu Lin ^1,2,*

1. School of Business Administration, Guizhou College of Finance and Economy, Guiyang China

2. Guizhou Key Laboratory of Economic Simulation, Guiyang China

* Corresponding author.

DOI: https://doi.org/10.5815/ijieeb.2009.01.01

Received: 12 Jul. 2009 / Revised: 5 Aug. 2009 / Accepted: 1 Sep. 2009 / Published: 8 Oct. 2009

Index Terms

Job shop scheduling under uncertain information, rough programming, maximum entropy estimation of distribution algorithm, test

Abstract

Estimation of Distribution Algorithm (EDA) is a new kinds of colony evolution algorithm, through counting excellent information of individuals of the present colony EDA construct probability distribution model, then sample the model produces newt generation. To solve the NP-Hard question as EDA searching optimum network structure a new Maximum Entropy Distribution Algorithm (MEEDA) is provided. The algorithm takes Jaynes principle as the basis, makes use of the maximum entropy of random variables to estimate the minimum bias probability distribution of random variables, and then regard it as the evolution model of the algorithm, which produces the optimal/near optimal solution. Then this paper presents a rough programming model for job shop scheduling under uncertain information problem. The method overcomes the defects of traditional methods which need pre-set authorized characteristics or amount described attributes, designs multi-objective optimization mechanism and expands the application space of a rough set in the issue of job shop scheduling under uncertain information environment. Due to the complexity of the proposed model, traditional algorithms have low capability in producing a feasible solution. We use MEEDA in order to enable a definition of a solution within a reasonable amount of time. We assume that machine flexibility in processing operations to decrease the complexity of the proposed model. Muth and Thompson’s benchmark problems tests are used to verify and validate the proposed rough programming model and its algorithm. The computational results obtained by MEEDA are compared with GA. The compared results prove the effectiveness of MEEDA in the job shop scheduling problem under uncertain information environment.

Cite This Paper

Lu Lin, "A New Maximum Entropy Estimation of Distribution Algorithm to Solve Uncertain Information Job-shop Scheduling Problem", International Journal of Information Engineering and Electronic Business(IJIEEB), vol.1, no.1, pp.1-8, 2009. DOI:10.5815/ijieeb.2009.01.01

Reference

[1]Larrañaga, P., Etxeberria, R., Lozano, J. A., Peña, J. M.: Optimization by learning and simulation of Bayesian and Gaussian networks. Technical Report EHU-KZAA-IK-4/99,University of the Basque Country, December 1999.
[2]Muhlenbein H, Paaβ G. “From Recombination of Genes to the Estimation of Distribution Algorithms I. Binary Parameters”. Parallel Problem Solving from Nature. Berlin: Springer, Vol. 4, 1996,pp.178-187.
[3]Zhang Q, Miihliebei H. “On the convergence of a class of estimation of distribution algorithms”. IEEE Trans on Evolutionary Computation. Vol.8, No. 2, 2004, pp. 127-136.
[4]J.A.LozanoP.Larraaga. Estimation of Distribution Algorithms.A New Tool for Evolutionary Computation.
[5]Martin Pelikan,David E.Goldberg,and Fernando Lobo. A survey of optimization by building and using prob-Abilistic models.IlliGAL Report No. 99018,Illinois Genetic Algorithms Laboratory,University of Illinois atUrbana-Champaign,Urbana, IL,1999.
[6]M.Pelikan. Bayesian optimization algorithm:From single level to hierarchy.PhD thesis,University of Illinois,2002.
[7]Siddall J.N. Probabilistic engineering design. Principles and Applications. New York: Marcel Dekker, 1983
[8]He Ting , Liu Fei ,Ma Yulin; Yang Hai. “Study on shop-floor scheduling”. Chinese Journal of Mechanical Engineering, Vol. 36, No.5, 2000,pp.97-102 (in Chinese).
[9]Jia, Z., & Ierapetritou, M. G. . Short-term scheduling under uncertainty using MILP sensitivity analysis. Industrial and Engineering Chemistry Research, 43, 2004,pp.3782–3791.
[10]Jia, Z., & Ierapetritou, M. G.. Uncertainty analysis on the right-handside for MILP problems. AIChE Journal, 52, 2006,pp.2486–2495.
[11]Zhang Guo-jun, Li Chan-juan, Zhu Hai-pin,etc. “A Hybrid Intelligent Algorithm for Job-shop Scheduling under Uncertain Information Environment”. Chinese Mechanical Engineering, Vol. 18 , No. 16, 2007,pp.1939-1942 (in Chinese).
[12]Xu Zhen-hao, GU Xing-shen. “Immune scheduling algorithm for flow shop problems under uncertaint”. Journal of Systems Engineering, Vol. 20, No. 4, 2005, pp.374-380 (in Chinese).
[13]Li Bing, Gu Xing-sheng. “Grey chance constrained programming for job shop scheduling under uncertainty”. Chinese High Technology Letters, Vol. 16, No. 10, 2006,pp.1025-1029 (in Chinese).
[14]Pawlak Z. “Rough sets”. International journal of computer and information sciences (S0091-7036), Vol. 11, No. 5, 1982, pp. 341-356.
[15]Yu Ai-qing，Gu Xing-sheng. “Flow Shop Scheduling Problem under Uncertainty Based on Generalized Rough Sets”. Journal of System Simulation, Vol. 18, No.12, 2006,pp.3369-3372, 3376 (in Chinese).
[16]Lingras P. “Unsupervised Rough Set Classification Using Gas”. Journal of Intelligent Information Systems (S0925-9902), Vol. 16, 2001, pp.215-228.
[17]Taillard E. “Benchmark for Basic Scheduling Problems”. European Journal of Operational Research (S0377-2217), Vol. 64, 1993, pp. 278-285.

International Journal of Information Engineering and Electronic Business (IJIEEB)