Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times

The problem addressed in this paper is the non-preemptive unrelated parallel machine scheduling problem with the objective of minimizing the makespan. Machine-dependent and job sequence-dependent setup times are considered, all jobs are available at time zero, and all times are deterministic. This i...

Full description

Saved in:
Bibliographic Details
Published in:Journal of intelligent manufacturing 2006-02, Vol.17 (1), p.85-97
Main Authors: Rabadi, Ghaith, Moraga, Reinaldo J., Al-Salem, Ameer
Format: Article
Language:English
Subjects:
Algorithms
Engineering
Heuristic
Heuristic methods
Job shops
Linear programming
Literature reviews
Manufacturing
Preempting
Production controls
Schedules
Scheduling
Setup times
Studies
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-c300t-5689353e4a9ebeecb070bea6f78ff683c58d178e9dafbf9284be2c7b7532ef6d3
cites cdi_FETCH-LOGICAL-c300t-5689353e4a9ebeecb070bea6f78ff683c58d178e9dafbf9284be2c7b7532ef6d3
container_end_page 97
container_issue 1
container_start_page 85
container_title Journal of intelligent manufacturing
container_volume 17
creator Rabadi, Ghaith
Moraga, Reinaldo J.
Al-Salem, Ameer
description The problem addressed in this paper is the non-preemptive unrelated parallel machine scheduling problem with the objective of minimizing the makespan. Machine-dependent and job sequence-dependent setup times are considered, all jobs are available at time zero, and all times are deterministic. This is a NP-hard problem and in this paper, optimal solutions are found for small problems only. For larger problems, a new meta-heuristic, Meta-RaPS, is introduced and its performance is evaluated by comparing its solutions to the solutions of an existing heuristic for the same problem. The results show that Meta-RaPS found all optimal solutions for the small problems and outperformed the solutions obtained by the existing heuristic for larger problems. [PUBLICATION ABSTRACT]
doi_str_mv 10.1007/s10845-005-5514-0
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2663836142</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2663836142</sourcerecordid><originalsourceid>FETCH-LOGICAL-c300t-5689353e4a9ebeecb070bea6f78ff683c58d178e9dafbf9284be2c7b7532ef6d3</originalsourceid><addsrcrecordid>eNp1kMtOwzAQRS0EEqXwAewsWAfGcfzIElXQIhVR1HZtOc6YpEqTYidC_D2pypbVLO65d6RDyC2DBwagHiMDnYkEQCRCsCyBMzJhQqWJZpk4JxPIhTwm4pJcxbgDgFxLNiEfCxxCHfvaReq7QPsK6bYN2NgeS7qywTYNNvTNuqpuka5dheXQ1O0nXYWuaHBPv-u-omvshwPd1HuM1-TC2ybizd-dku3L82a2SJbv89fZ0zJxHKBPhNQ5Fxwzm2OB6ApQUKCVXmnvpeZO6JIpjXlpfeHzVGcFpk4VSvAUvSz5lNyfdg-h-xow9mbXDaEdX5pUSq65ZFk6Unf_UqMsnopcjRA7QS50MQb05hDqvQ0_hoE56jUnvWZsmKNeA_wX_3dtRQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>200532597</pqid></control><display><type>article</type><title>Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times</title><source>ABI/INFORM Global</source><source>Springer Link</source><creator>Rabadi, Ghaith ; Moraga, Reinaldo J. ; Al-Salem, Ameer</creator><creatorcontrib>Rabadi, Ghaith ; Moraga, Reinaldo J. ; Al-Salem, Ameer</creatorcontrib><description>The problem addressed in this paper is the non-preemptive unrelated parallel machine scheduling problem with the objective of minimizing the makespan. Machine-dependent and job sequence-dependent setup times are considered, all jobs are available at time zero, and all times are deterministic. This is a NP-hard problem and in this paper, optimal solutions are found for small problems only. For larger problems, a new meta-heuristic, Meta-RaPS, is introduced and its performance is evaluated by comparing its solutions to the solutions of an existing heuristic for the same problem. The results show that Meta-RaPS found all optimal solutions for the small problems and outperformed the solutions obtained by the existing heuristic for larger problems. [PUBLICATION ABSTRACT]</description><identifier>ISSN: 0956-5515</identifier><identifier>EISSN: 1572-8145</identifier><identifier>DOI: 10.1007/s10845-005-5514-0</identifier><language>eng</language><publisher>London: Springer Nature B.V</publisher><subject>Algorithms ; Engineering ; Heuristic ; Heuristic methods ; Job shops ; Linear programming ; Literature reviews ; Manufacturing ; Preempting ; Production controls ; Schedules ; Scheduling ; Setup times ; Studies</subject><ispartof>Journal of intelligent manufacturing, 2006-02, Vol.17 (1), p.85-97</ispartof><rights>Springer Science+Business Media, Inc. 2006</rights><rights>Springer Science+Business Media, Inc. 2006.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c300t-5689353e4a9ebeecb070bea6f78ff683c58d178e9dafbf9284be2c7b7532ef6d3</citedby><cites>FETCH-LOGICAL-c300t-5689353e4a9ebeecb070bea6f78ff683c58d178e9dafbf9284be2c7b7532ef6d3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/200532597/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/200532597?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11688,27924,27925,36060,44363,74895</link.rule.ids></links><search><creatorcontrib>Rabadi, Ghaith</creatorcontrib><creatorcontrib>Moraga, Reinaldo J.</creatorcontrib><creatorcontrib>Al-Salem, Ameer</creatorcontrib><title>Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times</title><title>Journal of intelligent manufacturing</title><description>The problem addressed in this paper is the non-preemptive unrelated parallel machine scheduling problem with the objective of minimizing the makespan. Machine-dependent and job sequence-dependent setup times are considered, all jobs are available at time zero, and all times are deterministic. This is a NP-hard problem and in this paper, optimal solutions are found for small problems only. For larger problems, a new meta-heuristic, Meta-RaPS, is introduced and its performance is evaluated by comparing its solutions to the solutions of an existing heuristic for the same problem. The results show that Meta-RaPS found all optimal solutions for the small problems and outperformed the solutions obtained by the existing heuristic for larger problems. [PUBLICATION ABSTRACT]</description><subject>Algorithms</subject><subject>Engineering</subject><subject>Heuristic</subject><subject>Heuristic methods</subject><subject>Job shops</subject><subject>Linear programming</subject><subject>Literature reviews</subject><subject>Manufacturing</subject><subject>Preempting</subject><subject>Production controls</subject><subject>Schedules</subject><subject>Scheduling</subject><subject>Setup times</subject><subject>Studies</subject><issn>0956-5515</issn><issn>1572-8145</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2006</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kMtOwzAQRS0EEqXwAewsWAfGcfzIElXQIhVR1HZtOc6YpEqTYidC_D2pypbVLO65d6RDyC2DBwagHiMDnYkEQCRCsCyBMzJhQqWJZpk4JxPIhTwm4pJcxbgDgFxLNiEfCxxCHfvaReq7QPsK6bYN2NgeS7qywTYNNvTNuqpuka5dheXQ1O0nXYWuaHBPv-u-omvshwPd1HuM1-TC2ybizd-dku3L82a2SJbv89fZ0zJxHKBPhNQ5Fxwzm2OB6ApQUKCVXmnvpeZO6JIpjXlpfeHzVGcFpk4VSvAUvSz5lNyfdg-h-xow9mbXDaEdX5pUSq65ZFk6Unf_UqMsnopcjRA7QS50MQb05hDqvQ0_hoE56jUnvWZsmKNeA_wX_3dtRQ</recordid><startdate>20060201</startdate><enddate>20060201</enddate><creator>Rabadi, Ghaith</creator><creator>Moraga, Reinaldo J.</creator><creator>Al-Salem, Ameer</creator><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7TB</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88E</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FJ</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FR3</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GHDGH</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>K9.</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M0S</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope></search><sort><creationdate>20060201</creationdate><title>Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times</title><author>Rabadi, Ghaith ; Moraga, Reinaldo J. ; Al-Salem, Ameer</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c300t-5689353e4a9ebeecb070bea6f78ff683c58d178e9dafbf9284be2c7b7532ef6d3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2006</creationdate><topic>Algorithms</topic><topic>Engineering</topic><topic>Heuristic</topic><topic>Heuristic methods</topic><topic>Job shops</topic><topic>Linear programming</topic><topic>Literature reviews</topic><topic>Manufacturing</topic><topic>Preempting</topic><topic>Production controls</topic><topic>Schedules</topic><topic>Scheduling</topic><topic>Setup times</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Rabadi, Ghaith</creatorcontrib><creatorcontrib>Moraga, Reinaldo J.</creatorcontrib><creatorcontrib>Al-Salem, Ameer</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Medical Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Hospital Premium Collection (Alumni Edition)</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Engineering Research Database</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>Health Research Premium Collection (Alumni)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ProQuest Health &amp; Medical Complete (Alumni)</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>Health &amp; Medical Collection (Alumni Edition)</collection><collection>Engineering Database</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><jtitle>Journal of intelligent manufacturing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Rabadi, Ghaith</au><au>Moraga, Reinaldo J.</au><au>Al-Salem, Ameer</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times</atitle><jtitle>Journal of intelligent manufacturing</jtitle><date>2006-02-01</date><risdate>2006</risdate><volume>17</volume><issue>1</issue><spage>85</spage><epage>97</epage><pages>85-97</pages><issn>0956-5515</issn><eissn>1572-8145</eissn><abstract>The problem addressed in this paper is the non-preemptive unrelated parallel machine scheduling problem with the objective of minimizing the makespan. Machine-dependent and job sequence-dependent setup times are considered, all jobs are available at time zero, and all times are deterministic. This is a NP-hard problem and in this paper, optimal solutions are found for small problems only. For larger problems, a new meta-heuristic, Meta-RaPS, is introduced and its performance is evaluated by comparing its solutions to the solutions of an existing heuristic for the same problem. The results show that Meta-RaPS found all optimal solutions for the small problems and outperformed the solutions obtained by the existing heuristic for larger problems. [PUBLICATION ABSTRACT]</abstract><cop>London</cop><pub>Springer Nature B.V</pub><doi>10.1007/s10845-005-5514-0</doi><tpages>13</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0956-5515
ispartof Journal of intelligent manufacturing, 2006-02, Vol.17 (1), p.85-97
issn 0956-5515
1572-8145
language eng
recordid cdi_proquest_journals_2663836142
source ABI/INFORM Global; Springer Link
subjects Algorithms
Engineering
Heuristic
Heuristic methods
Job shops
Linear programming
Literature reviews
Manufacturing
Preempting
Production controls
Schedules
Scheduling
Setup times
Studies
title Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-28T18%3A31%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=Heuristics%20for%20the%20Unrelated%20Parallel%20Machine%20Scheduling%20Problem%20with%20Setup%20Times&rft.jtitle=Journal%20of%20intelligent%20manufacturing&rft.au=Rabadi,%20Ghaith&rft.date=2006-02-01&rft.volume=17&rft.issue=1&rft.spage=85&rft.epage=97&rft.pages=85-97&rft.issn=0956-5515&rft.eissn=1572-8145&rft_id=info:doi/10.1007/s10845-005-5514-0&rft_dat=%3Cproquest_cross%3E2663836142%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c300t-5689353e4a9ebeecb070bea6f78ff683c58d178e9dafbf9284be2c7b7532ef6d3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=200532597&rft_id=info:pmid/&rfr_iscdi=true