An estimation of distribution algorithm (EDA) variant with QGA for Flowshop scheduling problem

Muhammad Shahid Latif; Zhou Hong; Amir Ali

doi:10.1117/12.2064054

16 April 2014 An estimation of distribution algorithm (EDA) variant with QGA for Flowshop scheduling problem

Muhammad Shahid Latif, Zhou Hong, Amir Ali

Proceedings Volume 9159, Sixth International Conference on Digital Image Processing (ICDIP 2014); 915908 (2014) https://doi.org/10.1117/12.2064054
Event: Sixth International Conference on Digital Image Processing, 2014, Athens, Greece

Abstract

In this research article, a hybrid approach is presented which based on well-known meta-heuristics algorithms. This study based on integration of Quantum Genetic Algorithm (QGA) and Estimation of Distribution Algorithm, EDA, (for simplicity we use Q-EDA) for flowshop scheduling, a well-known NP hard Problem, while focusing on the total flow time minimization criterion. A relatively new method has been adopted for the encoding of jobs sequence in flowshop known as angel rotations instead of random keys, so QGA become more efficient. Further, EDA has been integrated to update the population of QGA by making a probability model. This probabilistic model is built and used to generate new candidate solutions which comprised on best individuals, obtained after several repetitions of proposed (Q-EDA) approach. As both heuristics based on probabilistic characteristics, so exhibits excellent learning capability and have minimum chances of being trapped in local optima. The results obtained during this study are presented and compared with contemporary approaches in literature. The current hybrid Q-EDA has implemented on different benchmark problems. The experiments has showed better convergence and results. It is concluded that hybrid Q-EDA algorithm can generally produce better results while implemented for Flowshop Scheduling Problem (FSSP).

Citation Download Citation

Muhammad Shahid Latif, Zhou Hong, and Amir Ali "An estimation of distribution algorithm (EDA) variant with QGA for Flowshop scheduling problem", Proc. SPIE 9159, Sixth International Conference on Digital Image Processing (ICDIP 2014), 915908 (16 April 2014); https://doi.org/10.1117/12.2064054

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available