File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Exact algorithms for distributionally β-robust machine scheduling with uncertain processing times

TitleExact algorithms for distributionally β-robust machine scheduling with uncertain processing times
Authors
KeywordsParametric search
β-robust scheduling
Distributionally robust
Speedup shortest augmentation path algorithm
Issue Date2018
Citation
INFORMS Journal on Computing, 2018, v. 30, n. 4, p. 662-676 How to Cite?
Abstract© 2018 INFORMS. The β-robust machine scheduling has attracted increasing attention as an effective method to hedge against uncertainty. However, existing β-robust scheduling models rely on the normality assumption of uncertain parameters, and existing solution methods are based on branch and bound, which cannot solve problems of 45 jobs within 3,600 seconds. This paper proposes distributionally β-robust scheduling (DRS) models to handle uncertain processing times. The DRS models only require the lower bound, mean, and covariance information of processing times, and have the capability of handling both single and parallel machine problems. Another key contribution of this paper is to devise efficient parametric search (PS) methods for the DRS models. Specifically, we show that there exists a parameterized assignment problem (PAP), such that its optimal solutions are also optimal for the original problem. The proposed methods only need to perform a one-dimensional PS and solve a series of PAPs. We further propose a bidirectional PS to reduce the number of PAPs needed to be solved, and we design a speedup shortest augmentation path algorithm for these PAPs. Experimental results on both single and identical parallel machine problems show that the improved PS method outperforms existing algorithms by more than three orders of magnitude improvement in computation time for problems of 45 jobs, and it is able to solve problems of 500 jobs within 0.5 seconds.
Persistent Identifierhttp://hdl.handle.net/10722/296272
ISSN
2023 Impact Factor: 2.3
2023 SCImago Journal Rankings: 1.264
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yuli-
dc.contributor.authorShen, Zuo Jun Max-
dc.contributor.authorSong, Shiji-
dc.date.accessioned2021-02-11T04:53:12Z-
dc.date.available2021-02-11T04:53:12Z-
dc.date.issued2018-
dc.identifier.citationINFORMS Journal on Computing, 2018, v. 30, n. 4, p. 662-676-
dc.identifier.issn1091-9856-
dc.identifier.urihttp://hdl.handle.net/10722/296272-
dc.description.abstract© 2018 INFORMS. The β-robust machine scheduling has attracted increasing attention as an effective method to hedge against uncertainty. However, existing β-robust scheduling models rely on the normality assumption of uncertain parameters, and existing solution methods are based on branch and bound, which cannot solve problems of 45 jobs within 3,600 seconds. This paper proposes distributionally β-robust scheduling (DRS) models to handle uncertain processing times. The DRS models only require the lower bound, mean, and covariance information of processing times, and have the capability of handling both single and parallel machine problems. Another key contribution of this paper is to devise efficient parametric search (PS) methods for the DRS models. Specifically, we show that there exists a parameterized assignment problem (PAP), such that its optimal solutions are also optimal for the original problem. The proposed methods only need to perform a one-dimensional PS and solve a series of PAPs. We further propose a bidirectional PS to reduce the number of PAPs needed to be solved, and we design a speedup shortest augmentation path algorithm for these PAPs. Experimental results on both single and identical parallel machine problems show that the improved PS method outperforms existing algorithms by more than three orders of magnitude improvement in computation time for problems of 45 jobs, and it is able to solve problems of 500 jobs within 0.5 seconds.-
dc.languageeng-
dc.relation.ispartofINFORMS Journal on Computing-
dc.subjectParametric search-
dc.subjectβ-robust scheduling-
dc.subjectDistributionally robust-
dc.subjectSpeedup shortest augmentation path algorithm-
dc.titleExact algorithms for distributionally β-robust machine scheduling with uncertain processing times-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1287/ijoc.2018.0807-
dc.identifier.scopuseid_2-s2.0-85053322124-
dc.identifier.volume30-
dc.identifier.issue4-
dc.identifier.spage662-
dc.identifier.epage676-
dc.identifier.eissn1526-5528-
dc.identifier.isiWOS:000458386100004-
dc.identifier.issnl1091-9856-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats