A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems
<p dir="ltr">This study investigates the no-wait flow shop scheduling problem and proposes a hybrid (HES-IG) algorithm that utilizes makespan as the objective function. To address the complexity of this NP-hard problem, the HES-IG algorithm combines evolution strategies (ES) and iter...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , , |
| Published: |
2024
|
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513510293110784 |
|---|---|
| author | Bilal Khurshid (16715865) |
| author2 | Shahid Maqsood (10325711) Yahya Khurshid (19205959) Khawar Naeem (17984062) Qazi Salman Khalid (17984056) |
| author2_role | author author author author |
| author_facet | Bilal Khurshid (16715865) Shahid Maqsood (10325711) Yahya Khurshid (19205959) Khawar Naeem (17984062) Qazi Salman Khalid (17984056) |
| author_role | author |
| dc.creator.none.fl_str_mv | Bilal Khurshid (16715865) Shahid Maqsood (10325711) Yahya Khurshid (19205959) Khawar Naeem (17984062) Qazi Salman Khalid (17984056) |
| dc.date.none.fl_str_mv | 2024-01-29T09:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1038/s41598-023-47729-x |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/A_hybridization_of_evolution_strategies_with_iterated_greedy_algorithm_for_no-wait_flow_shop_scheduling_problems/26363101 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Engineering Manufacturing engineering Mathematical sciences Applied mathematics Hybrid algorithm (HES-IG) Makespan Evolution strategies (ES) Iterated greedy (IG) algorithm NP-hard problem Lower bound values |
| dc.title.none.fl_str_mv | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p dir="ltr">This study investigates the no-wait flow shop scheduling problem and proposes a hybrid (HES-IG) algorithm that utilizes makespan as the objective function. To address the complexity of this NP-hard problem, the HES-IG algorithm combines evolution strategies (ES) and iterated greedy (IG) algorithm, as hybridizing algorithms helps different algorithms mitigate their weaknesses and leverage their respective strengths. The ES algorithm begins with a random initial solution and uses an insertion mutation to optimize the solution. Reproduction is carried out using (1 + 5)-ES, generating five offspring from one parent randomly. The selection process employs (µ + λ)-ES, allowing excellent parent solutions to survive multiple generations until a better offspring surpasses them. The IG algorithm’s straightforward search mechanism aids in further improving the solution and avoiding local minima. The destruction operator randomly removes d-jobs, which are then inserted one by one using a construction operator. The local search operator employs a single insertion approach, while the acceptance–rejection criteria are based on a constant temperature. Parameters of both ES and IG algorithms are calibrated using the Multifactor analysis of variance technique. The performance of the HES-IG algorithm is calibrated with other algorithms using the Wilcoxon signed test. The HES-IG algorithm is tested on 21 Nos. Reeves and 30 Nos. Taillard benchmark problems. The HES-IG algorithm has found 15 lower bound values for Reeves benchmark problems. Similarly, the HES-IG algorithm has found 30 lower bound values for the Taillard benchmark problems. Computational results indicate that the HES-IG algorithm outperforms other available techniques in the literature for all problem sizes.</p><h2>Other Information</h2><p dir="ltr">Published in: Scientific Reports<br>License: <a href="https://creativecommons.org/licenses/by/4.0" target="_blank">https://creativecommons.org/licenses/by/4.0</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1038/s41598-023-47729-x" target="_blank">https://dx.doi.org/10.1038/s41598-023-47729-x</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_7d1cb3e8fa82eb5589f2639c5dd4b8a6 |
| identifier_str_mv | 10.1038/s41598-023-47729-x |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/26363101 |
| publishDate | 2024 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problemsBilal Khurshid (16715865)Shahid Maqsood (10325711)Yahya Khurshid (19205959)Khawar Naeem (17984062)Qazi Salman Khalid (17984056)EngineeringManufacturing engineeringMathematical sciencesApplied mathematicsHybrid algorithm (HES-IG)MakespanEvolution strategies (ES)Iterated greedy (IG) algorithmNP-hard problemLower bound values<p dir="ltr">This study investigates the no-wait flow shop scheduling problem and proposes a hybrid (HES-IG) algorithm that utilizes makespan as the objective function. To address the complexity of this NP-hard problem, the HES-IG algorithm combines evolution strategies (ES) and iterated greedy (IG) algorithm, as hybridizing algorithms helps different algorithms mitigate their weaknesses and leverage their respective strengths. The ES algorithm begins with a random initial solution and uses an insertion mutation to optimize the solution. Reproduction is carried out using (1 + 5)-ES, generating five offspring from one parent randomly. The selection process employs (µ + λ)-ES, allowing excellent parent solutions to survive multiple generations until a better offspring surpasses them. The IG algorithm’s straightforward search mechanism aids in further improving the solution and avoiding local minima. The destruction operator randomly removes d-jobs, which are then inserted one by one using a construction operator. The local search operator employs a single insertion approach, while the acceptance–rejection criteria are based on a constant temperature. Parameters of both ES and IG algorithms are calibrated using the Multifactor analysis of variance technique. The performance of the HES-IG algorithm is calibrated with other algorithms using the Wilcoxon signed test. The HES-IG algorithm is tested on 21 Nos. Reeves and 30 Nos. Taillard benchmark problems. The HES-IG algorithm has found 15 lower bound values for Reeves benchmark problems. Similarly, the HES-IG algorithm has found 30 lower bound values for the Taillard benchmark problems. Computational results indicate that the HES-IG algorithm outperforms other available techniques in the literature for all problem sizes.</p><h2>Other Information</h2><p dir="ltr">Published in: Scientific Reports<br>License: <a href="https://creativecommons.org/licenses/by/4.0" target="_blank">https://creativecommons.org/licenses/by/4.0</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1038/s41598-023-47729-x" target="_blank">https://dx.doi.org/10.1038/s41598-023-47729-x</a></p>2024-01-29T09:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1038/s41598-023-47729-xhttps://figshare.com/articles/journal_contribution/A_hybridization_of_evolution_strategies_with_iterated_greedy_algorithm_for_no-wait_flow_shop_scheduling_problems/26363101CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/263631012024-01-29T09:00:00Z |
| spellingShingle | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems Bilal Khurshid (16715865) Engineering Manufacturing engineering Mathematical sciences Applied mathematics Hybrid algorithm (HES-IG) Makespan Evolution strategies (ES) Iterated greedy (IG) algorithm NP-hard problem Lower bound values |
| status_str | publishedVersion |
| title | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems |
| title_full | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems |
| title_fullStr | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems |
| title_full_unstemmed | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems |
| title_short | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems |
| title_sort | A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems |
| topic | Engineering Manufacturing engineering Mathematical sciences Applied mathematics Hybrid algorithm (HES-IG) Makespan Evolution strategies (ES) Iterated greedy (IG) algorithm NP-hard problem Lower bound values |