Investigating the recoverable robust single machine scheduling problem under interval uncertainty

We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2022-05, Vol.313, p.99-114
Main Authors: Bold, Matthew, Goerigk, Marc
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Integer programming
Job shops
Mathematical analysis
Mixed integer
Optimisation under uncertainty
Polynomials
Recoverable robustness
Robustness
Schedules
Scheduling
Uncertainty
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-c368t-a3136f197b822fab0c55bd35177c764f418168a2d375d6be170b700c2e1f17b53
cites cdi_FETCH-LOGICAL-c368t-a3136f197b822fab0c55bd35177c764f418168a2d375d6be170b700c2e1f17b53
container_end_page 114
container_issue
container_start_page 99
container_title Discrete Applied Mathematics
container_volume 313
creator Bold, Matthew
Goerigk, Marc
description We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least Δ jobs share the same position in both schedules. We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic.
doi_str_mv 10.1016/j.dam.2022.02.005
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2654393217</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0166218X22000427</els_id><sourcerecordid>2654393217</sourcerecordid><originalsourceid>FETCH-LOGICAL-c368t-a3136f197b822fab0c55bd35177c764f418168a2d375d6be170b700c2e1f17b53</originalsourceid><addsrcrecordid>eNp9UE1Lw0AQXUTBWv0B3gKeE3c2zW6KJyl-FApeFLwtm82k3ZCPupsE-u-dUM_CwMxj3puPx9g98AQ4yMc6KU2bCC5Ewil4dsEWkCsRS6Xgki2II2MB-fc1uwmh5pwDoQUz227CMLi9GVy3j4YDRh5tP6E3RUN1X4xhiAL1CLXGHlyHUbAHLMdmFhyJ0WAbjV2JPnLdgH4yDUGLfjCET7fsqjJNwLu_vGRfry-fm_d49_G23TzvYpvKfIhNCqmsYK2KXIjKFNxmWVGmGShllVxVK8hB5kaUqcpKWSAoXijOrUCoQBVZumQP57l00s9IP-m6H31HK7WQ2SpdpwIUseDMsr4PwWOlj961xp80cD07qWtNTurZSc0p-Dz56axBOn9y6HWwDunD0pFXgy5794_6F9I5fOg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2654393217</pqid></control><display><type>article</type><title>Investigating the recoverable robust single machine scheduling problem under interval uncertainty</title><source>Elsevier</source><creator>Bold, Matthew ; Goerigk, Marc</creator><creatorcontrib>Bold, Matthew ; Goerigk, Marc</creatorcontrib><description>We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least Δ jobs share the same position in both schedules. We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic.</description><identifier>ISSN: 0166-218X</identifier><identifier>EISSN: 1872-6771</identifier><identifier>DOI: 10.1016/j.dam.2022.02.005</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algorithms ; Approximation ; Integer programming ; Job shops ; Mathematical analysis ; Mixed integer ; Optimisation under uncertainty ; Polynomials ; Recoverable robustness ; Robustness ; Schedules ; Scheduling ; Uncertainty</subject><ispartof>Discrete Applied Mathematics, 2022-05, Vol.313, p.99-114</ispartof><rights>2022 The Authors</rights><rights>Copyright Elsevier BV May 31, 2022</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c368t-a3136f197b822fab0c55bd35177c764f418168a2d375d6be170b700c2e1f17b53</citedby><cites>FETCH-LOGICAL-c368t-a3136f197b822fab0c55bd35177c764f418168a2d375d6be170b700c2e1f17b53</cites><orcidid>0000-0002-2516-0129 ; 0000-0003-2200-796X</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Bold, Matthew</creatorcontrib><creatorcontrib>Goerigk, Marc</creatorcontrib><title>Investigating the recoverable robust single machine scheduling problem under interval uncertainty</title><title>Discrete Applied Mathematics</title><description>We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least Δ jobs share the same position in both schedules. We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic.</description><subject>Algorithms</subject><subject>Approximation</subject><subject>Integer programming</subject><subject>Job shops</subject><subject>Mathematical analysis</subject><subject>Mixed integer</subject><subject>Optimisation under uncertainty</subject><subject>Polynomials</subject><subject>Recoverable robustness</subject><subject>Robustness</subject><subject>Schedules</subject><subject>Scheduling</subject><subject>Uncertainty</subject><issn>0166-218X</issn><issn>1872-6771</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><recordid>eNp9UE1Lw0AQXUTBWv0B3gKeE3c2zW6KJyl-FApeFLwtm82k3ZCPupsE-u-dUM_CwMxj3puPx9g98AQ4yMc6KU2bCC5Ewil4dsEWkCsRS6Xgki2II2MB-fc1uwmh5pwDoQUz227CMLi9GVy3j4YDRh5tP6E3RUN1X4xhiAL1CLXGHlyHUbAHLMdmFhyJ0WAbjV2JPnLdgH4yDUGLfjCET7fsqjJNwLu_vGRfry-fm_d49_G23TzvYpvKfIhNCqmsYK2KXIjKFNxmWVGmGShllVxVK8hB5kaUqcpKWSAoXijOrUCoQBVZumQP57l00s9IP-m6H31HK7WQ2SpdpwIUseDMsr4PwWOlj961xp80cD07qWtNTurZSc0p-Dz56axBOn9y6HWwDunD0pFXgy5794_6F9I5fOg</recordid><startdate>20220531</startdate><enddate>20220531</enddate><creator>Bold, Matthew</creator><creator>Goerigk, Marc</creator><general>Elsevier B.V</general><general>Elsevier BV</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0002-2516-0129</orcidid><orcidid>https://orcid.org/0000-0003-2200-796X</orcidid></search><sort><creationdate>20220531</creationdate><title>Investigating the recoverable robust single machine scheduling problem under interval uncertainty</title><author>Bold, Matthew ; Goerigk, Marc</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c368t-a3136f197b822fab0c55bd35177c764f418168a2d375d6be170b700c2e1f17b53</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Approximation</topic><topic>Integer programming</topic><topic>Job shops</topic><topic>Mathematical analysis</topic><topic>Mixed integer</topic><topic>Optimisation under uncertainty</topic><topic>Polynomials</topic><topic>Recoverable robustness</topic><topic>Robustness</topic><topic>Schedules</topic><topic>Scheduling</topic><topic>Uncertainty</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Bold, Matthew</creatorcontrib><creatorcontrib>Goerigk, Marc</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science 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><jtitle>Discrete Applied Mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Bold, Matthew</au><au>Goerigk, Marc</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Investigating the recoverable robust single machine scheduling problem under interval uncertainty</atitle><jtitle>Discrete Applied Mathematics</jtitle><date>2022-05-31</date><risdate>2022</risdate><volume>313</volume><spage>99</spage><epage>114</epage><pages>99-114</pages><issn>0166-218X</issn><eissn>1872-6771</eissn><abstract>We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least Δ jobs share the same position in both schedules. We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/j.dam.2022.02.005</doi><tpages>16</tpages><orcidid>https://orcid.org/0000-0002-2516-0129</orcidid><orcidid>https://orcid.org/0000-0003-2200-796X</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0166-218X
ispartof Discrete Applied Mathematics, 2022-05, Vol.313, p.99-114
issn 0166-218X
1872-6771
language eng
recordid cdi_proquest_journals_2654393217
source Elsevier
subjects Algorithms
Approximation
Integer programming
Job shops
Mathematical analysis
Mixed integer
Optimisation under uncertainty
Polynomials
Recoverable robustness
Robustness
Schedules
Scheduling
Uncertainty
title Investigating the recoverable robust single machine scheduling problem under interval uncertainty
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-02T12%3A43%3A45IST&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=Investigating%20the%20recoverable%20robust%20single%20machine%20scheduling%20problem%20under%20interval%20uncertainty&rft.jtitle=Discrete%20Applied%20Mathematics&rft.au=Bold,%20Matthew&rft.date=2022-05-31&rft.volume=313&rft.spage=99&rft.epage=114&rft.pages=99-114&rft.issn=0166-218X&rft.eissn=1872-6771&rft_id=info:doi/10.1016/j.dam.2022.02.005&rft_dat=%3Cproquest_cross%3E2654393217%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c368t-a3136f197b822fab0c55bd35177c764f418168a2d375d6be170b700c2e1f17b53%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2654393217&rft_id=info:pmid/&rfr_iscdi=true