An Improved Genetic-Simulated Annealing Algorithm Based on a Hormone Modulation Mechanism for a Flexible Flow-Shop Scheduling Problem
A flexible flow-shop scheduling (FFS) with nonidentical parallel machines for minimizing the maximum completion time or makespan is a well-known combinational problem. Since the problem is known to be strongly NP-hard, optimization can either be the subject of optimization approaches or be implement...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SAGE Publishing
2013-01-01
|
| Series: | Advances in Mechanical Engineering |
| Online Access: | https://doi.org/10.1155/2013/124903 |
| _version_ | 1818478860413435904 |
|---|---|
| author | Min Dai Dunbing Tang Kun Zheng Qixiang Cai |
| author_facet | Min Dai Dunbing Tang Kun Zheng Qixiang Cai |
| author_sort | Min Dai |
| collection | DOAJ |
| description | A flexible flow-shop scheduling (FFS) with nonidentical parallel machines for minimizing the maximum completion time or makespan is a well-known combinational problem. Since the problem is known to be strongly NP-hard, optimization can either be the subject of optimization approaches or be implemented for some approximated cases. In this paper, an improved genetic-simulated annealing algorithm (IGAA), which combines genetic algorithm (GA) based on an encoding matrix with simulated annealing algorithm (SAA) based on a hormone modulation mechanism, is proposed to achieve the optimal or near-optimal solution. The novel hybrid algorithm tries to overcome the local optimum and further to explore the solution space. To evaluate the performance of IGAA, computational experiments are conducted and compared with results generated by different algorithms. Experimental results clearly demonstrate that the improved metaheuristic algorithm performs considerably well in terms of solution quality, and it outperforms several other algorithms. |
| first_indexed | 2024-12-10T09:53:26Z |
| format | Article |
| id | doaj.art-d3febd5bcc3b4e0fac25eddafede18c1 |
| institution | Directory Open Access Journal |
| issn | 1687-8132 |
| language | English |
| last_indexed | 2024-12-10T09:53:26Z |
| publishDate | 2013-01-01 |
| publisher | SAGE Publishing |
| record_format | Article |
| series | Advances in Mechanical Engineering |
| spelling | doaj.art-d3febd5bcc3b4e0fac25eddafede18c12022-12-22T01:53:35ZengSAGE PublishingAdvances in Mechanical Engineering1687-81322013-01-01510.1155/2013/12490310.1155_2013/124903An Improved Genetic-Simulated Annealing Algorithm Based on a Hormone Modulation Mechanism for a Flexible Flow-Shop Scheduling ProblemMin Dai0Dunbing Tang1Kun Zheng2Qixiang Cai3 Jiangsu Key Laboratory of Precision and Micro-Manufacturing Technology, Nanjing 210016, China Jiangsu Key Laboratory of Precision and Micro-Manufacturing Technology, Nanjing 210016, China Jiangsu Key Laboratory of Precision and Micro-Manufacturing Technology, Nanjing 210016, China Jiangsu Key Laboratory of Precision and Micro-Manufacturing Technology, Nanjing 210016, ChinaA flexible flow-shop scheduling (FFS) with nonidentical parallel machines for minimizing the maximum completion time or makespan is a well-known combinational problem. Since the problem is known to be strongly NP-hard, optimization can either be the subject of optimization approaches or be implemented for some approximated cases. In this paper, an improved genetic-simulated annealing algorithm (IGAA), which combines genetic algorithm (GA) based on an encoding matrix with simulated annealing algorithm (SAA) based on a hormone modulation mechanism, is proposed to achieve the optimal or near-optimal solution. The novel hybrid algorithm tries to overcome the local optimum and further to explore the solution space. To evaluate the performance of IGAA, computational experiments are conducted and compared with results generated by different algorithms. Experimental results clearly demonstrate that the improved metaheuristic algorithm performs considerably well in terms of solution quality, and it outperforms several other algorithms.https://doi.org/10.1155/2013/124903 |
| spellingShingle | Min Dai Dunbing Tang Kun Zheng Qixiang Cai An Improved Genetic-Simulated Annealing Algorithm Based on a Hormone Modulation Mechanism for a Flexible Flow-Shop Scheduling Problem Advances in Mechanical Engineering |
| title | An Improved Genetic-Simulated Annealing Algorithm Based on a Hormone Modulation Mechanism for a Flexible Flow-Shop Scheduling Problem |
| title_full | An Improved Genetic-Simulated Annealing Algorithm Based on a Hormone Modulation Mechanism for a Flexible Flow-Shop Scheduling Problem |
| title_fullStr | An Improved Genetic-Simulated Annealing Algorithm Based on a Hormone Modulation Mechanism for a Flexible Flow-Shop Scheduling Problem |
| title_full_unstemmed | An Improved Genetic-Simulated Annealing Algorithm Based on a Hormone Modulation Mechanism for a Flexible Flow-Shop Scheduling Problem |
| title_short | An Improved Genetic-Simulated Annealing Algorithm Based on a Hormone Modulation Mechanism for a Flexible Flow-Shop Scheduling Problem |
| title_sort | improved genetic simulated annealing algorithm based on a hormone modulation mechanism for a flexible flow shop scheduling problem |
| url | https://doi.org/10.1155/2013/124903 |
| work_keys_str_mv | AT mindai animprovedgeneticsimulatedannealingalgorithmbasedonahormonemodulationmechanismforaflexibleflowshopschedulingproblem AT dunbingtang animprovedgeneticsimulatedannealingalgorithmbasedonahormonemodulationmechanismforaflexibleflowshopschedulingproblem AT kunzheng animprovedgeneticsimulatedannealingalgorithmbasedonahormonemodulationmechanismforaflexibleflowshopschedulingproblem AT qixiangcai animprovedgeneticsimulatedannealingalgorithmbasedonahormonemodulationmechanismforaflexibleflowshopschedulingproblem AT mindai improvedgeneticsimulatedannealingalgorithmbasedonahormonemodulationmechanismforaflexibleflowshopschedulingproblem AT dunbingtang improvedgeneticsimulatedannealingalgorithmbasedonahormonemodulationmechanismforaflexibleflowshopschedulingproblem AT kunzheng improvedgeneticsimulatedannealingalgorithmbasedonahormonemodulationmechanismforaflexibleflowshopschedulingproblem AT qixiangcai improvedgeneticsimulatedannealingalgorithmbasedonahormonemodulationmechanismforaflexibleflowshopschedulingproblem |