Effect of solution representations on Tabu search in scheduling applications

Chen Fu Chen, Muh-Cherng Wu*, Keng Han Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


This research investigates the application of meta-heuristic algorithms to a scheduling problem called permutation manufacturing-cell flow shop (PMFS) from two perspectives. First, we examine the effect of using different solution representations (Snew and Sold) while applying Tabu-search algorithm. Experimental results reveal that Tabu-Snew outperforms Tabu-Sold. The rationale why Tabu-Snew is superior is further examined by characterizing the intermediate outcomes of the evolutionary processes in these two algorithms. We find that the superiority of S new is due to its relatively higher degree of freedom in modeling Tabu neighborhood. Second, we propose a new algorithm GA-Tabu-Snew, which empirically outperforms the state-of-the-art meta-heuristic algorithms in solving the PMFS problem. This research highlights the importance of solution representation in the application of meta-heuristic algorithm, and establishes a significant milestone in solving the PMFS problem.

Original languageEnglish
Pages (from-to)2817-2825
Number of pages9
JournalComputers and Operations Research
Issue number12
StatePublished - 23 Jul 2013


  • Flow shop
  • Scheduling
  • Solution representation
  • Tabu search

Fingerprint Dive into the research topics of 'Effect of solution representations on Tabu search in scheduling applications'. Together they form a unique fingerprint.

Cite this