A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times

This article deals with the problem of scheduling n jobs on m identical parallel processors with the objective of minimizing the total execution time (makespan). A new three-phase heuristic is proposed for solving this problem. An initial phase constructs a starting solution which is improved, in a...

Full description

Saved in:
Bibliographic Details
Published in:International journal of production economics 1996-06, Vol.43 (2), p.79-89
Main Authors: França, Paulo M., Gendreau, Michel, Laporte, Gilbert, Müller, Felipe M.
Format: Article
Language:English
Subjects:
Economic models
Heuristic
Heuristics
Job shops
Local search
Multiprocessor scheduling
Parallel processing
Searches
Sequential scheduling
Studies
Tabu search
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-c429t-5666b8d6f1b62e3b66170ad7938c5dce0e6e57b99e72f70f5defa779bd81ebfe3
cites cdi_FETCH-LOGICAL-c429t-5666b8d6f1b62e3b66170ad7938c5dce0e6e57b99e72f70f5defa779bd81ebfe3
container_end_page 89
container_issue 2
container_start_page 79
container_title International journal of production economics
container_volume 43
creator França, Paulo M.
Gendreau, Michel
Laporte, Gilbert
Müller, Felipe M.
description This article deals with the problem of scheduling n jobs on m identical parallel processors with the objective of minimizing the total execution time (makespan). A new three-phase heuristic is proposed for solving this problem. An initial phase constructs a starting solution which is improved, in a second phase, by means of a tabu search method. A final phase follows attempting a further improvement in the current solution. Numerical tests in a series of randomly generated problems indicate that the proposed method outperforms a previous heuristic. Comparisons with an exact procedure attest that our method produces good-quality solutions in reasonable running times.
doi_str_mv 10.1016/0925-5273(96)00031-X
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_198945701</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>092552739600031X</els_id><sourcerecordid>10286142</sourcerecordid><originalsourceid>FETCH-LOGICAL-c429t-5666b8d6f1b62e3b66170ad7938c5dce0e6e57b99e72f70f5defa779bd81ebfe3</originalsourceid><addsrcrecordid>eNp9UE1LxDAUDKLg-vEPPARPeqgmzTZpLoKInwheFPYW2uTVRrYfJumK_95XVjx6eAkZZuZNhpATzi444_KS6bzIilyJMy3PGWOCZ6sdsuClEpkqlN4liz_KPjmI8QNJipflgsA1TVU90QhVsC1tYQo-Jm9pMwSaWqDdtE5-DIOFGBGKtgU3rX3_ThGs19DRL59a1H9O0FugDkboHfQJoTSNNPkO4hHZa6p1hOPf-5C83d2-3jxkzy_3jzfXz5ld5jplhZSyLp1seC1zELWUXLHKKS1KWzgLDCQUqtYaVN4o1hQOmkopXbuSQ92AOCSnW1_MhnliMh_DFHpcabgu9bJQjCNpuSXZMMQYoDFj8F0Vvg1nZu7TzGWZuSyj8TH3aVYoe9rKAv7Q_mkAAJeBHczGiGop8PjG4RqlovI4uZnBEUdpU2rTpg7NrrZmgG1sPAQTrZ_7cz6ATcYN_v80PyiBmIs</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>198945701</pqid></control><display><type>article</type><title>A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times</title><source>ScienceDirect Freedom Collection</source><creator>França, Paulo M. ; Gendreau, Michel ; Laporte, Gilbert ; Müller, Felipe M.</creator><creatorcontrib>França, Paulo M. ; Gendreau, Michel ; Laporte, Gilbert ; Müller, Felipe M.</creatorcontrib><description>This article deals with the problem of scheduling n jobs on m identical parallel processors with the objective of minimizing the total execution time (makespan). A new three-phase heuristic is proposed for solving this problem. An initial phase constructs a starting solution which is improved, in a second phase, by means of a tabu search method. A final phase follows attempting a further improvement in the current solution. Numerical tests in a series of randomly generated problems indicate that the proposed method outperforms a previous heuristic. Comparisons with an exact procedure attest that our method produces good-quality solutions in reasonable running times.</description><identifier>ISSN: 0925-5273</identifier><identifier>EISSN: 1873-7579</identifier><identifier>DOI: 10.1016/0925-5273(96)00031-X</identifier><identifier>CODEN: IJPCEY</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Economic models ; Heuristic ; Heuristics ; Job shops ; Local search ; Multiprocessor scheduling ; Parallel processing ; Searches ; Sequential scheduling ; Studies ; Tabu search</subject><ispartof>International journal of production economics, 1996-06, Vol.43 (2), p.79-89</ispartof><rights>1996</rights><rights>Copyright Elsevier Sequoia S.A. Jun 1, 1996</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c429t-5666b8d6f1b62e3b66170ad7938c5dce0e6e57b99e72f70f5defa779bd81ebfe3</citedby><cites>FETCH-LOGICAL-c429t-5666b8d6f1b62e3b66170ad7938c5dce0e6e57b99e72f70f5defa779bd81ebfe3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27903,27904</link.rule.ids><backlink>$$Uhttp://econpapers.repec.org/article/eeeproeco/v_3a43_3ay_3a1996_3ai_3a2-3_3ap_3a79-89.htm$$DView record in RePEc$$Hfree_for_read</backlink></links><search><creatorcontrib>França, Paulo M.</creatorcontrib><creatorcontrib>Gendreau, Michel</creatorcontrib><creatorcontrib>Laporte, Gilbert</creatorcontrib><creatorcontrib>Müller, Felipe M.</creatorcontrib><title>A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times</title><title>International journal of production economics</title><description>This article deals with the problem of scheduling n jobs on m identical parallel processors with the objective of minimizing the total execution time (makespan). A new three-phase heuristic is proposed for solving this problem. An initial phase constructs a starting solution which is improved, in a second phase, by means of a tabu search method. A final phase follows attempting a further improvement in the current solution. Numerical tests in a series of randomly generated problems indicate that the proposed method outperforms a previous heuristic. Comparisons with an exact procedure attest that our method produces good-quality solutions in reasonable running times.</description><subject>Economic models</subject><subject>Heuristic</subject><subject>Heuristics</subject><subject>Job shops</subject><subject>Local search</subject><subject>Multiprocessor scheduling</subject><subject>Parallel processing</subject><subject>Searches</subject><subject>Sequential scheduling</subject><subject>Studies</subject><subject>Tabu search</subject><issn>0925-5273</issn><issn>1873-7579</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1996</creationdate><recordtype>article</recordtype><recordid>eNp9UE1LxDAUDKLg-vEPPARPeqgmzTZpLoKInwheFPYW2uTVRrYfJumK_95XVjx6eAkZZuZNhpATzi444_KS6bzIilyJMy3PGWOCZ6sdsuClEpkqlN4liz_KPjmI8QNJipflgsA1TVU90QhVsC1tYQo-Jm9pMwSaWqDdtE5-DIOFGBGKtgU3rX3_ThGs19DRL59a1H9O0FugDkboHfQJoTSNNPkO4hHZa6p1hOPf-5C83d2-3jxkzy_3jzfXz5ld5jplhZSyLp1seC1zELWUXLHKKS1KWzgLDCQUqtYaVN4o1hQOmkopXbuSQ92AOCSnW1_MhnliMh_DFHpcabgu9bJQjCNpuSXZMMQYoDFj8F0Vvg1nZu7TzGWZuSyj8TH3aVYoe9rKAv7Q_mkAAJeBHczGiGop8PjG4RqlovI4uZnBEUdpU2rTpg7NrrZmgG1sPAQTrZ_7cz6ATcYN_v80PyiBmIs</recordid><startdate>19960601</startdate><enddate>19960601</enddate><creator>França, Paulo M.</creator><creator>Gendreau, Michel</creator><creator>Laporte, Gilbert</creator><creator>Müller, Felipe M.</creator><general>Elsevier B.V</general><general>Elsevier</general><general>Elsevier Sequoia S.A</general><scope>DKI</scope><scope>X2L</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7TA</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>JG9</scope><scope>KR7</scope></search><sort><creationdate>19960601</creationdate><title>A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times</title><author>França, Paulo M. ; Gendreau, Michel ; Laporte, Gilbert ; Müller, Felipe M.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c429t-5666b8d6f1b62e3b66170ad7938c5dce0e6e57b99e72f70f5defa779bd81ebfe3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1996</creationdate><topic>Economic models</topic><topic>Heuristic</topic><topic>Heuristics</topic><topic>Job shops</topic><topic>Local search</topic><topic>Multiprocessor scheduling</topic><topic>Parallel processing</topic><topic>Searches</topic><topic>Sequential scheduling</topic><topic>Studies</topic><topic>Tabu search</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>França, Paulo M.</creatorcontrib><creatorcontrib>Gendreau, Michel</creatorcontrib><creatorcontrib>Laporte, Gilbert</creatorcontrib><creatorcontrib>Müller, Felipe M.</creatorcontrib><collection>RePEc IDEAS</collection><collection>RePEc</collection><collection>CrossRef</collection><collection>Materials Business File</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering Research Database</collection><collection>Materials Research Database</collection><collection>Civil Engineering Abstracts</collection><jtitle>International journal of production economics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>França, Paulo M.</au><au>Gendreau, Michel</au><au>Laporte, Gilbert</au><au>Müller, Felipe M.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times</atitle><jtitle>International journal of production economics</jtitle><date>1996-06-01</date><risdate>1996</risdate><volume>43</volume><issue>2</issue><spage>79</spage><epage>89</epage><pages>79-89</pages><issn>0925-5273</issn><eissn>1873-7579</eissn><coden>IJPCEY</coden><abstract>This article deals with the problem of scheduling n jobs on m identical parallel processors with the objective of minimizing the total execution time (makespan). A new three-phase heuristic is proposed for solving this problem. An initial phase constructs a starting solution which is improved, in a second phase, by means of a tabu search method. A final phase follows attempting a further improvement in the current solution. Numerical tests in a series of randomly generated problems indicate that the proposed method outperforms a previous heuristic. Comparisons with an exact procedure attest that our method produces good-quality solutions in reasonable running times.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/0925-5273(96)00031-X</doi><tpages>11</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0925-5273
ispartof International journal of production economics, 1996-06, Vol.43 (2), p.79-89
issn 0925-5273
1873-7579
language eng
recordid cdi_proquest_journals_198945701
source ScienceDirect Freedom Collection
subjects Economic models
Heuristic
Heuristics
Job shops
Local search
Multiprocessor scheduling
Parallel processing
Searches
Sequential scheduling
Studies
Tabu search
title A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-27T00%3A18%3A21IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20tabu%20search%20heuristic%20for%20the%20multiprocessor%20scheduling%20problem%20with%20sequence%20dependent%20setup%20times&rft.jtitle=International%20journal%20of%20production%20economics&rft.au=Fran%C3%A7a,%20Paulo%20M.&rft.date=1996-06-01&rft.volume=43&rft.issue=2&rft.spage=79&rft.epage=89&rft.pages=79-89&rft.issn=0925-5273&rft.eissn=1873-7579&rft.coden=IJPCEY&rft_id=info:doi/10.1016/0925-5273(96)00031-X&rft_dat=%3Cproquest_cross%3E10286142%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c429t-5666b8d6f1b62e3b66170ad7938c5dce0e6e57b99e72f70f5defa779bd81ebfe3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=198945701&rft_id=info:pmid/&rfr_iscdi=true