Loading…
Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time
In this paper, we study the resolution of a permutation flow shop problem with sequence-independent setup time. The objective is to minimize the maximum of job completion time, also called the makespan. In this contribution, we propose three methods of resolution, a mixed-integer linear programming...
Saved in:
| Published in: | Journal of applied mathematics 2020, Vol.2020 (2020), p.1-11 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c465t-f9e20b2a76135b4e74f6ff13e195bdfe87964f116a43422ec55da34fc6c1e2f63 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c465t-f9e20b2a76135b4e74f6ff13e195bdfe87964f116a43422ec55da34fc6c1e2f63 |
| container_end_page | 11 |
| container_issue | 2020 |
| container_start_page | 1 |
| container_title | Journal of applied mathematics |
| container_volume | 2020 |
| creator | Belabid, Jabrane Allali, Karam Aqil, Said |
| description | In this paper, we study the resolution of a permutation flow shop problem with sequence-independent setup time. The objective is to minimize the maximum of job completion time, also called the makespan. In this contribution, we propose three methods of resolution, a mixed-integer linear programming (MILP) model; two heuristics, the first based on Johnson’s rule and the second based on the NEH algorithm; and finally two metaheuristics, the iterative local search algorithm and the iterated greedy algorithm. A set of test problems is simulated numerically to validate the effectiveness of our resolution approaches. For relatively small-size problems, it has been revealed that the adapted NEH heuristic has the best performance than that of the Johnson-based heuristic. For the relatively medium and large problems, the comparative study between the two metaheuristics based on the exploration of the neighborhood shows that the iterated greedy algorithm records the best performances. |
| doi_str_mv | 10.1155/2020/7132469 |
| format | article |
| fullrecord | <record><control><sourceid>gale_doaj_</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_856931718fd8408d8cd5d374c36f403e</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A622150061</galeid><doaj_id>oai_doaj_org_article_856931718fd8408d8cd5d374c36f403e</doaj_id><sourcerecordid>A622150061</sourcerecordid><originalsourceid>FETCH-LOGICAL-c465t-f9e20b2a76135b4e74f6ff13e195bdfe87964f116a43422ec55da34fc6c1e2f63</originalsourceid><addsrcrecordid>eNqFkd1rFDEUxYMoWFfffJYBH3Xa3HzOPJZidaGgsC34FrLJzW6WmcmYme3if2-2U_TRBJJw-N3DvTmEvAd6CSDlFaOMXmngTKj2BbkA1eiaUsFeljcArbXUP1-TN9N0oIWULVyQh03qHuOwq35g7o-znWMaqtsunarNPo3Vxu3RH7snIKdth311ivO-2uCvIw4O6_XgccRyDHMR5-NY3cce35JXwXYTvnu-V-Th9sv9zbf67vvX9c31Xe2EknMdWmR0y6xWwOVWoBZBhQAcoZVbH7DRrRIBQFnBBWPopPSWi-CUA2RB8RVZL74-2YMZc-xt_m2SjeZJSHlnbJ6j69A0UrUcNDTBN4I2vnFeeq6F4yoIyrF4fVy8xpzKcNNsDumYh9K-YVyeP4yXtSKXC7WzxTQOIc3ZurI99tGlAUMs-rViDEpNmWtFPi8FLqdpyhj-tgnUnFMz59TMc2oF_7Tg-zh4e4r_oz8sNBYGg_1HgxZSKf4HYBSfDA</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2350020333</pqid></control><display><type>article</type><title>Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time</title><source>Publicly Available Content Database</source><source>Wiley Open Access Journals</source><creator>Belabid, Jabrane ; Allali, Karam ; Aqil, Said</creator><contributor>Krithivasan, Kannan ; Kannan Krithivasan</contributor><creatorcontrib>Belabid, Jabrane ; Allali, Karam ; Aqil, Said ; Krithivasan, Kannan ; Kannan Krithivasan</creatorcontrib><description>In this paper, we study the resolution of a permutation flow shop problem with sequence-independent setup time. The objective is to minimize the maximum of job completion time, also called the makespan. In this contribution, we propose three methods of resolution, a mixed-integer linear programming (MILP) model; two heuristics, the first based on Johnson’s rule and the second based on the NEH algorithm; and finally two metaheuristics, the iterative local search algorithm and the iterated greedy algorithm. A set of test problems is simulated numerically to validate the effectiveness of our resolution approaches. For relatively small-size problems, it has been revealed that the adapted NEH heuristic has the best performance than that of the Johnson-based heuristic. For the relatively medium and large problems, the comparative study between the two metaheuristics based on the exploration of the neighborhood shows that the iterated greedy algorithm records the best performances.</description><identifier>ISSN: 1110-757X</identifier><identifier>EISSN: 1687-0042</identifier><identifier>DOI: 10.1155/2020/7132469</identifier><language>eng</language><publisher>Cairo, Egypt: Hindawi Publishing Corporation</publisher><subject>Algorithms ; Analysis ; Comparative studies ; Completion time ; Computer simulation ; Greedy algorithms ; Heuristic ; Heuristic methods ; Integer programming ; Iterative methods ; Job shop scheduling ; Job shops ; Linear programming ; Neighborhoods ; Optimization algorithms ; Permutations ; Production scheduling ; Researchers ; Search algorithms ; Sequential scheduling ; Setup times ; Water waves</subject><ispartof>Journal of applied mathematics, 2020, Vol.2020 (2020), p.1-11</ispartof><rights>Copyright © 2020 Jabrane Belabid et al.</rights><rights>COPYRIGHT 2020 John Wiley & Sons, Inc.</rights><rights>Copyright © 2020 Jabrane Belabid et al. This is an open access article distributed under the Creative Commons Attribution License (the “License”), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License. http://creativecommons.org/licenses/by/4.0</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c465t-f9e20b2a76135b4e74f6ff13e195bdfe87964f116a43422ec55da34fc6c1e2f63</citedby><cites>FETCH-LOGICAL-c465t-f9e20b2a76135b4e74f6ff13e195bdfe87964f116a43422ec55da34fc6c1e2f63</cites><orcidid>0000-0002-9463-4295 ; 0000-0002-7337-2927</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2350020333/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2350020333?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>314,776,780,4009,25732,27902,27903,27904,36991,44569,74872</link.rule.ids></links><search><contributor>Krithivasan, Kannan</contributor><contributor>Kannan Krithivasan</contributor><creatorcontrib>Belabid, Jabrane</creatorcontrib><creatorcontrib>Allali, Karam</creatorcontrib><creatorcontrib>Aqil, Said</creatorcontrib><title>Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time</title><title>Journal of applied mathematics</title><description>In this paper, we study the resolution of a permutation flow shop problem with sequence-independent setup time. The objective is to minimize the maximum of job completion time, also called the makespan. In this contribution, we propose three methods of resolution, a mixed-integer linear programming (MILP) model; two heuristics, the first based on Johnson’s rule and the second based on the NEH algorithm; and finally two metaheuristics, the iterative local search algorithm and the iterated greedy algorithm. A set of test problems is simulated numerically to validate the effectiveness of our resolution approaches. For relatively small-size problems, it has been revealed that the adapted NEH heuristic has the best performance than that of the Johnson-based heuristic. For the relatively medium and large problems, the comparative study between the two metaheuristics based on the exploration of the neighborhood shows that the iterated greedy algorithm records the best performances.</description><subject>Algorithms</subject><subject>Analysis</subject><subject>Comparative studies</subject><subject>Completion time</subject><subject>Computer simulation</subject><subject>Greedy algorithms</subject><subject>Heuristic</subject><subject>Heuristic methods</subject><subject>Integer programming</subject><subject>Iterative methods</subject><subject>Job shop scheduling</subject><subject>Job shops</subject><subject>Linear programming</subject><subject>Neighborhoods</subject><subject>Optimization algorithms</subject><subject>Permutations</subject><subject>Production scheduling</subject><subject>Researchers</subject><subject>Search algorithms</subject><subject>Sequential scheduling</subject><subject>Setup times</subject><subject>Water waves</subject><issn>1110-757X</issn><issn>1687-0042</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><sourceid>DOA</sourceid><recordid>eNqFkd1rFDEUxYMoWFfffJYBH3Xa3HzOPJZidaGgsC34FrLJzW6WmcmYme3if2-2U_TRBJJw-N3DvTmEvAd6CSDlFaOMXmngTKj2BbkA1eiaUsFeljcArbXUP1-TN9N0oIWULVyQh03qHuOwq35g7o-znWMaqtsunarNPo3Vxu3RH7snIKdth311ivO-2uCvIw4O6_XgccRyDHMR5-NY3cce35JXwXYTvnu-V-Th9sv9zbf67vvX9c31Xe2EknMdWmR0y6xWwOVWoBZBhQAcoZVbH7DRrRIBQFnBBWPopPSWi-CUA2RB8RVZL74-2YMZc-xt_m2SjeZJSHlnbJ6j69A0UrUcNDTBN4I2vnFeeq6F4yoIyrF4fVy8xpzKcNNsDumYh9K-YVyeP4yXtSKXC7WzxTQOIc3ZurI99tGlAUMs-rViDEpNmWtFPi8FLqdpyhj-tgnUnFMz59TMc2oF_7Tg-zh4e4r_oz8sNBYGg_1HgxZSKf4HYBSfDA</recordid><startdate>2020</startdate><enddate>2020</enddate><creator>Belabid, Jabrane</creator><creator>Allali, Karam</creator><creator>Aqil, Said</creator><general>Hindawi Publishing Corporation</general><general>Hindawi</general><general>John Wiley & Sons, Inc</general><general>Hindawi Limited</general><scope>ADJCN</scope><scope>AHFXO</scope><scope>RHU</scope><scope>RHW</scope><scope>RHX</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7TB</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>CWDGH</scope><scope>DWQXO</scope><scope>FR3</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>KR7</scope><scope>L6V</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>DOA</scope><orcidid>https://orcid.org/0000-0002-9463-4295</orcidid><orcidid>https://orcid.org/0000-0002-7337-2927</orcidid></search><sort><creationdate>2020</creationdate><title>Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time</title><author>Belabid, Jabrane ; Allali, Karam ; Aqil, Said</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c465t-f9e20b2a76135b4e74f6ff13e195bdfe87964f116a43422ec55da34fc6c1e2f63</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Algorithms</topic><topic>Analysis</topic><topic>Comparative studies</topic><topic>Completion time</topic><topic>Computer simulation</topic><topic>Greedy algorithms</topic><topic>Heuristic</topic><topic>Heuristic methods</topic><topic>Integer programming</topic><topic>Iterative methods</topic><topic>Job shop scheduling</topic><topic>Job shops</topic><topic>Linear programming</topic><topic>Neighborhoods</topic><topic>Optimization algorithms</topic><topic>Permutations</topic><topic>Production scheduling</topic><topic>Researchers</topic><topic>Search algorithms</topic><topic>Sequential scheduling</topic><topic>Setup times</topic><topic>Water waves</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Belabid, Jabrane</creatorcontrib><creatorcontrib>Allali, Karam</creatorcontrib><creatorcontrib>Aqil, Said</creatorcontrib><collection>الدوريات العلمية والإحصائية - e-Marefa Academic and Statistical Periodicals</collection><collection>معرفة - المحتوى العربي الأكاديمي المتكامل - e-Marefa Academic Complete</collection><collection>Hindawi Publishing Complete</collection><collection>Hindawi Publishing Subscription Journals</collection><collection>Hindawi Publishing Open Access Journals</collection><collection>CrossRef</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies & Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>Middle East & Africa Database</collection><collection>ProQuest Central</collection><collection>Engineering Research Database</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>Civil Engineering Abstracts</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>ProQuest advanced technologies & aerospace journals</collection><collection>ProQuest Advanced Technologies & Aerospace Collection</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection><collection>DOAJ Directory of Open Access Journals</collection><jtitle>Journal of applied mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Belabid, Jabrane</au><au>Allali, Karam</au><au>Aqil, Said</au><au>Krithivasan, Kannan</au><au>Kannan Krithivasan</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time</atitle><jtitle>Journal of applied mathematics</jtitle><date>2020</date><risdate>2020</risdate><volume>2020</volume><issue>2020</issue><spage>1</spage><epage>11</epage><pages>1-11</pages><issn>1110-757X</issn><eissn>1687-0042</eissn><abstract>In this paper, we study the resolution of a permutation flow shop problem with sequence-independent setup time. The objective is to minimize the maximum of job completion time, also called the makespan. In this contribution, we propose three methods of resolution, a mixed-integer linear programming (MILP) model; two heuristics, the first based on Johnson’s rule and the second based on the NEH algorithm; and finally two metaheuristics, the iterative local search algorithm and the iterated greedy algorithm. A set of test problems is simulated numerically to validate the effectiveness of our resolution approaches. For relatively small-size problems, it has been revealed that the adapted NEH heuristic has the best performance than that of the Johnson-based heuristic. For the relatively medium and large problems, the comparative study between the two metaheuristics based on the exploration of the neighborhood shows that the iterated greedy algorithm records the best performances.</abstract><cop>Cairo, Egypt</cop><pub>Hindawi Publishing Corporation</pub><doi>10.1155/2020/7132469</doi><tpages>11</tpages><orcidid>https://orcid.org/0000-0002-9463-4295</orcidid><orcidid>https://orcid.org/0000-0002-7337-2927</orcidid><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 1110-757X |
| ispartof | Journal of applied mathematics, 2020, Vol.2020 (2020), p.1-11 |
| issn | 1110-757X 1687-0042 |
| language | eng |
| recordid | cdi_doaj_primary_oai_doaj_org_article_856931718fd8408d8cd5d374c36f403e |
| source | Publicly Available Content Database; Wiley Open Access Journals |
| subjects | Algorithms Analysis Comparative studies Completion time Computer simulation Greedy algorithms Heuristic Heuristic methods Integer programming Iterative methods Job shop scheduling Job shops Linear programming Neighborhoods Optimization algorithms Permutations Production scheduling Researchers Search algorithms Sequential scheduling Setup times Water waves |
| title | Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-27T00%3A00%3A54IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_doaj_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Solving%20Permutation%20Flow%20Shop%20Scheduling%20Problem%20with%20Sequence-Independent%20Setup%20Time&rft.jtitle=Journal%20of%20applied%20mathematics&rft.au=Belabid,%20Jabrane&rft.date=2020&rft.volume=2020&rft.issue=2020&rft.spage=1&rft.epage=11&rft.pages=1-11&rft.issn=1110-757X&rft.eissn=1687-0042&rft_id=info:doi/10.1155/2020/7132469&rft_dat=%3Cgale_doaj_%3EA622150061%3C/gale_doaj_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c465t-f9e20b2a76135b4e74f6ff13e195bdfe87964f116a43422ec55da34fc6c1e2f63%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2350020333&rft_id=info:pmid/&rft_galeid=A622150061&rfr_iscdi=true |