A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems
The m-machine, n-job, permutation flowshop problem with the total tardiness objective is a common scheduling problem, known to be NP-hard. Branch and bound, the usual approach to finding an optimal solution, experiences difficulty when n exceeds 20. Here, we develop a genetic algorithm, GA, which ca...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cognitione Foundation for the Dissemination of Knowledge and Science
2012-01-01
|
| Series: | Journal of Entrepreneurship, Management and Innovation |
| Subjects: | |
| Online Access: |
http://jemi.edu.pl/uploadedFiles/file/all-issues/vol8/issue2/JEMI_Vol_8_Issue_2_2012_Article_2.pdf
|
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832568747696586752 |
|---|---|
| author | Chia-Shin Chung James Flynn Walter Rom Piotr Staliński |
| author_facet | Chia-Shin Chung James Flynn Walter Rom Piotr Staliński |
| author_sort | Chia-Shin Chung |
| collection | DOAJ |
| description | The m-machine, n-job, permutation flowshop problem with the total tardiness objective is a common scheduling problem, known to be NP-hard. Branch and bound, the usual approach to finding an optimal solution, experiences difficulty when n exceeds 20. Here, we develop a genetic algorithm, GA, which can handle problems with larger n. We also undertake a numerical study comparing GA with an optimal branch and bound algorithm, and various heuristic algorithms including the well known NEH algorithm and a local search heuristic LH. Extensive computational experiments indicate that LH is an effective heuristic and GA can produce noticeable improvements over LH. |
| format | Article |
| id | doaj-art-f931c9c91a884419a6f945ad1d3dcc73 |
| institution | Kabale University |
| issn | 2299-7326 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Cognitione Foundation for the Dissemination of Knowledge and Science |
| record_format | Article |
| series | Journal of Entrepreneurship, Management and Innovation |
| spelling | doaj-art-f931c9c91a884419a6f945ad1d3dcc732025-02-03T00:45:48ZengCognitione Foundation for the Dissemination of Knowledge and ScienceJournal of Entrepreneurship, Management and Innovation2299-73262012-01-0182264310.7341/2012822A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop ProblemsChia-Shin Chung0James Flynn1Walter Rom2Piotr Staliński Department of Operations and Supply Chain Management, Cleveland State Univesity Department of Operations and Supply Chain Management, Cleveland State Univesity Department of Quantitative Methods in Management, Wyższa Szkoła Biznesu-National Louis University The m-machine, n-job, permutation flowshop problem with the total tardiness objective is a common scheduling problem, known to be NP-hard. Branch and bound, the usual approach to finding an optimal solution, experiences difficulty when n exceeds 20. Here, we develop a genetic algorithm, GA, which can handle problems with larger n. We also undertake a numerical study comparing GA with an optimal branch and bound algorithm, and various heuristic algorithms including the well known NEH algorithm and a local search heuristic LH. Extensive computational experiments indicate that LH is an effective heuristic and GA can produce noticeable improvements over LH. http://jemi.edu.pl/uploadedFiles/file/all-issues/vol8/issue2/JEMI_Vol_8_Issue_2_2012_Article_2.pdf genetic algorithmschedulingpermutation flowshoptardiness |
| spellingShingle | Chia-Shin Chung James Flynn Walter Rom Piotr Staliński A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems Journal of Entrepreneurship, Management and Innovation genetic algorithm scheduling permutation flowshop tardiness |
| title | A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems |
| title_full | A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems |
| title_fullStr | A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems |
| title_full_unstemmed | A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems |
| title_short | A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems |
| title_sort | genetic algorithm to minimize the total tardiness for m machine permutation flowshop problems |
| topic | genetic algorithm scheduling permutation flowshop tardiness |
| url |
http://jemi.edu.pl/uploadedFiles/file/all-issues/vol8/issue2/JEMI_Vol_8_Issue_2_2012_Article_2.pdf
|
| work_keys_str_mv | AT chiashinchung ageneticalgorithmtominimizethetotaltardinessformmachinepermutationflowshopproblems AT jamesflynn ageneticalgorithmtominimizethetotaltardinessformmachinepermutationflowshopproblems AT walterrom ageneticalgorithmtominimizethetotaltardinessformmachinepermutationflowshopproblems AT piotrstalinski ageneticalgorithmtominimizethetotaltardinessformmachinepermutationflowshopproblems AT chiashinchung geneticalgorithmtominimizethetotaltardinessformmachinepermutationflowshopproblems AT jamesflynn geneticalgorithmtominimizethetotaltardinessformmachinepermutationflowshopproblems AT walterrom geneticalgorithmtominimizethetotaltardinessformmachinepermutationflowshopproblems AT piotrstalinski geneticalgorithmtominimizethetotaltardinessformmachinepermutationflowshopproblems |