Bounds for parallel machine scheduling with predefined parts of jobs and setup time

We examine a parallel machine scheduling problem with setup time in order to minimize the makespan. Each job consists of predefined parts, and the parts of a job can be processed concurrently in different machines. We first provide worst-case bounds of the Longest Processing Time and list schedules...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2018-02, Vol.261 (1-2), p.401-412
Main Author: Kim, Hyun-Jung
Format: Article
Language:English
Subjects:
Algorithms
Business and Management
Combinatorics
Heuristic methods
Industrial equipment
Job shops
Management science
Operations research
Operations Research/Decision Theory
Parallel processing
Printers
Production scheduling
Schedules
Scheduling
Scheduling (Management)
Setup times
Short Note
Theory of Computation
Three dimensional printing
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-c490t-b2ab9f1ae511d291defd79e4a2a6082ed29de4c43b6034166e8c043131fdd16a3
cites cdi_FETCH-LOGICAL-c490t-b2ab9f1ae511d291defd79e4a2a6082ed29de4c43b6034166e8c043131fdd16a3
container_end_page 412
container_issue 1-2
container_start_page 401
container_title Annals of operations research
container_volume 261
creator Kim, Hyun-Jung
description We examine a parallel machine scheduling problem with setup time in order to minimize the makespan. Each job consists of predefined parts, and the parts of a job can be processed concurrently in different machines. We first provide worst-case bounds of the Longest Processing Time and list schedules for special cases. We also develop a heuristic algorithm for scheduling parts of jobs with family setup time and propose its worst-case performance ratio. The application is the IoT-based smart factory with 3D printers as processing machines.
doi_str_mv 10.1007/s10479-017-2615-z
format article
fullrecord <record><control><sourceid>gale_proqu</sourceid><recordid>TN_cdi_proquest_journals_1992797862</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A523273866</galeid><sourcerecordid>A523273866</sourcerecordid><originalsourceid>FETCH-LOGICAL-c490t-b2ab9f1ae511d291defd79e4a2a6082ed29de4c43b6034166e8c043131fdd16a3</originalsourceid><addsrcrecordid>eNp1kVFr1TAUx4MoeJ37AHsL-Gq3nKRNm8c5nAoDH6bPIW1Oe3Npm5rTIu7TL5cruMEkkMDJ73fCyZ-xCxCXIER9RSDK2hQC6kJqqIqHV2wHVS0Lo1Tzmu2ErMqiUkq8Ze-IDkIIgKbasftPcZs98T4mvrjkxhFHPrluH2bk1O3Rb2OYB_47rHu-JPTY5xt_ZFfiseeH2BJ3s-eE67bwNUz4nr3p3Uh4_vc8Yz9vP_-4-Vrcff_y7eb6ruhKI9aila41PTisALw0kFv72mDppNOikZhrHsuuVK0WqgStselEqUBB7z1op87Yh1PfJcVfG9JqD3FLc37SgjGyNnWj5T9qcCPaMPdxTa6bAnX2upJK1qrROlOXL1B5eZxCF-c8dq4_Ez4-EdqN8rdQ3igM-5UGtxE9x-GEdykSJeztksLk0h8Lwh4TtKcEbU7QHhO0D9mRJ4cyOw-Ynsz3X-kRQMudQQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1992797862</pqid></control><display><type>article</type><title>Bounds for parallel machine scheduling with predefined parts of jobs and setup time</title><source>Business Source Ultimate【Trial: -2024/12/31】【Remote access available】</source><source>ABI/INFORM Global</source><source>Springer Nature</source><creator>Kim, Hyun-Jung</creator><creatorcontrib>Kim, Hyun-Jung</creatorcontrib><description>We examine a parallel machine scheduling problem with setup time in order to minimize the makespan. Each job consists of predefined parts, and the parts of a job can be processed concurrently in different machines. We first provide worst-case bounds of the Longest Processing Time and list schedules for special cases. We also develop a heuristic algorithm for scheduling parts of jobs with family setup time and propose its worst-case performance ratio. The application is the IoT-based smart factory with 3D printers as processing machines.</description><identifier>ISSN: 0254-5330</identifier><identifier>EISSN: 1572-9338</identifier><identifier>DOI: 10.1007/s10479-017-2615-z</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Algorithms ; Business and Management ; Combinatorics ; Heuristic methods ; Industrial equipment ; Job shops ; Management science ; Operations research ; Operations Research/Decision Theory ; Parallel processing ; Printers ; Production scheduling ; Schedules ; Scheduling ; Scheduling (Management) ; Setup times ; Short Note ; Theory of Computation ; Three dimensional printing</subject><ispartof>Annals of operations research, 2018-02, Vol.261 (1-2), p.401-412</ispartof><rights>Springer Science+Business Media, LLC 2017</rights><rights>COPYRIGHT 2018 Springer</rights><rights>Annals of Operations Research is a copyright of Springer, (2017). All Rights Reserved.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c490t-b2ab9f1ae511d291defd79e4a2a6082ed29de4c43b6034166e8c043131fdd16a3</citedby><cites>FETCH-LOGICAL-c490t-b2ab9f1ae511d291defd79e4a2a6082ed29de4c43b6034166e8c043131fdd16a3</cites><orcidid>0000-0001-7190-3264</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/1992797862/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/1992797862?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11686,27922,27923,36058,44361,74665</link.rule.ids></links><search><creatorcontrib>Kim, Hyun-Jung</creatorcontrib><title>Bounds for parallel machine scheduling with predefined parts of jobs and setup time</title><title>Annals of operations research</title><addtitle>Ann Oper Res</addtitle><description>We examine a parallel machine scheduling problem with setup time in order to minimize the makespan. Each job consists of predefined parts, and the parts of a job can be processed concurrently in different machines. We first provide worst-case bounds of the Longest Processing Time and list schedules for special cases. We also develop a heuristic algorithm for scheduling parts of jobs with family setup time and propose its worst-case performance ratio. The application is the IoT-based smart factory with 3D printers as processing machines.</description><subject>Algorithms</subject><subject>Business and Management</subject><subject>Combinatorics</subject><subject>Heuristic methods</subject><subject>Industrial equipment</subject><subject>Job shops</subject><subject>Management science</subject><subject>Operations research</subject><subject>Operations Research/Decision Theory</subject><subject>Parallel processing</subject><subject>Printers</subject><subject>Production scheduling</subject><subject>Schedules</subject><subject>Scheduling</subject><subject>Scheduling (Management)</subject><subject>Setup times</subject><subject>Short Note</subject><subject>Theory of Computation</subject><subject>Three dimensional printing</subject><issn>0254-5330</issn><issn>1572-9338</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kVFr1TAUx4MoeJ37AHsL-Gq3nKRNm8c5nAoDH6bPIW1Oe3Npm5rTIu7TL5cruMEkkMDJ73fCyZ-xCxCXIER9RSDK2hQC6kJqqIqHV2wHVS0Lo1Tzmu2ErMqiUkq8Ze-IDkIIgKbasftPcZs98T4mvrjkxhFHPrluH2bk1O3Rb2OYB_47rHu-JPTY5xt_ZFfiseeH2BJ3s-eE67bwNUz4nr3p3Uh4_vc8Yz9vP_-4-Vrcff_y7eb6ruhKI9aila41PTisALw0kFv72mDppNOikZhrHsuuVK0WqgStselEqUBB7z1op87Yh1PfJcVfG9JqD3FLc37SgjGyNnWj5T9qcCPaMPdxTa6bAnX2upJK1qrROlOXL1B5eZxCF-c8dq4_Ez4-EdqN8rdQ3igM-5UGtxE9x-GEdykSJeztksLk0h8Lwh4TtKcEbU7QHhO0D9mRJ4cyOw-Ynsz3X-kRQMudQQ</recordid><startdate>20180201</startdate><enddate>20180201</enddate><creator>Kim, Hyun-Jung</creator><general>Springer US</general><general>Springer</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>N95</scope><scope>3V.</scope><scope>7TA</scope><scope>7TB</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</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>GNUQQ</scope><scope>HCIFZ</scope><scope>JG9</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KR7</scope><scope>L.-</scope><scope>L6V</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</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><orcidid>https://orcid.org/0000-0001-7190-3264</orcidid></search><sort><creationdate>20180201</creationdate><title>Bounds for parallel machine scheduling with predefined parts of jobs and setup time</title><author>Kim, Hyun-Jung</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c490t-b2ab9f1ae511d291defd79e4a2a6082ed29de4c43b6034166e8c043131fdd16a3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Algorithms</topic><topic>Business and Management</topic><topic>Combinatorics</topic><topic>Heuristic methods</topic><topic>Industrial equipment</topic><topic>Job shops</topic><topic>Management science</topic><topic>Operations research</topic><topic>Operations Research/Decision Theory</topic><topic>Parallel processing</topic><topic>Printers</topic><topic>Production scheduling</topic><topic>Schedules</topic><topic>Scheduling</topic><topic>Scheduling (Management)</topic><topic>Setup times</topic><topic>Short Note</topic><topic>Theory of Computation</topic><topic>Three dimensional printing</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Kim, Hyun-Jung</creatorcontrib><collection>CrossRef</collection><collection>Gale Business Insights</collection><collection>ProQuest Central (Corporate)</collection><collection>Materials Business File</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>ABI商业信息数据库</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Science 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>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>AUTh Library subscriptions: 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>ProQuest Central Student</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>Materials Research Database</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>Civil Engineering Abstracts</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>ProQuest Science Journals</collection><collection>Engineering Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest 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>Annals of operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Kim, Hyun-Jung</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Bounds for parallel machine scheduling with predefined parts of jobs and setup time</atitle><jtitle>Annals of operations research</jtitle><stitle>Ann Oper Res</stitle><date>2018-02-01</date><risdate>2018</risdate><volume>261</volume><issue>1-2</issue><spage>401</spage><epage>412</epage><pages>401-412</pages><issn>0254-5330</issn><eissn>1572-9338</eissn><abstract>We examine a parallel machine scheduling problem with setup time in order to minimize the makespan. Each job consists of predefined parts, and the parts of a job can be processed concurrently in different machines. We first provide worst-case bounds of the Longest Processing Time and list schedules for special cases. We also develop a heuristic algorithm for scheduling parts of jobs with family setup time and propose its worst-case performance ratio. The application is the IoT-based smart factory with 3D printers as processing machines.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s10479-017-2615-z</doi><tpages>12</tpages><orcidid>https://orcid.org/0000-0001-7190-3264</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0254-5330
ispartof Annals of operations research, 2018-02, Vol.261 (1-2), p.401-412
issn 0254-5330
1572-9338
language eng
recordid cdi_proquest_journals_1992797862
source Business Source Ultimate【Trial: -2024/12/31】【Remote access available】; ABI/INFORM Global; Springer Nature
subjects Algorithms
Business and Management
Combinatorics
Heuristic methods
Industrial equipment
Job shops
Management science
Operations research
Operations Research/Decision Theory
Parallel processing
Printers
Production scheduling
Schedules
Scheduling
Scheduling (Management)
Setup times
Short Note
Theory of Computation
Three dimensional printing
title Bounds for parallel machine scheduling with predefined parts of jobs and 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-09T10%3A20%3A32IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_proqu&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Bounds%20for%20parallel%20machine%20scheduling%20with%20predefined%20parts%20of%20jobs%20and%20setup%20time&rft.jtitle=Annals%20of%20operations%20research&rft.au=Kim,%20Hyun-Jung&rft.date=2018-02-01&rft.volume=261&rft.issue=1-2&rft.spage=401&rft.epage=412&rft.pages=401-412&rft.issn=0254-5330&rft.eissn=1572-9338&rft_id=info:doi/10.1007/s10479-017-2615-z&rft_dat=%3Cgale_proqu%3EA523273866%3C/gale_proqu%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c490t-b2ab9f1ae511d291defd79e4a2a6082ed29de4c43b6034166e8c043131fdd16a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1992797862&rft_id=info:pmid/&rft_galeid=A523273866&rfr_iscdi=true