Volume 9 Number 9 (Sep. 2014)
Home > Archive > 2014 > Volume 9 Number 9 (Sep. 2014) >
JCP 2014 Vol.9(9): 2191-2197 ISSN: 1796-203X
doi: 10.4304/jcp.9.9.2191-2197

A Novel Variant of QGA with VNS for Flowshop Scheduling Problem

Muhammad Shahid Latif1, Hong Zhou1, Amir Ali2
1Beihang University of Aeronautics and Astronautics, Beijing, China School of Economics and Management
2Beihang University of Aeronautics and Astronautics, Beijing, China School of Computer Science and Engineering

Abstract—In this paper, scheduling problem of flowshop with the criterion of minimizing the total flow time has been considered. An effective hybrid Quantum Genetic Algorithm and Variable Neighborhood Search (QGA-VNS or QGAVNS) has been proposed as solution of Flow Shop Scheduling Problem (FSSP). First, the QGA is considered for global search in optimal solution and then VNS has been integrated for enhancing the local search capability. An adaptive two-point crossover and quantum interference operator (QIC) has been used in quantum chromosomes, which is based on the probability learning and quality of solution at each iteration. Further, a Longest Common Sequence (LCS) method has been adopted to construct the neighborhood solutions for intensifying local search with VNS. The neighborhood solutions will be based on the common sequence similar to the longest common sequence in global solution in each iteration, represented as LCSg. After selection of individual, VNS will be applied further exploring the local search space based on LCS neighborhood solutions. Results and comparisons with different algorithms based on the famous benchmarks demonstrates the effectiveness of proposed QGA-VNS.

Index Terms—Flowshop scheduling, QGA, VNS, LCS, Quantum Population

[PDF]

Cite: Muhammad Shahid Latif, Hong Zhou, Amir Ali, "A Novel Variant of QGA with VNS for Flowshop Scheduling Problem," Journal of Computers vol. 9, no. 9, pp. 2191-2197, 2014.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>