Exact Algorithms for Distributionally β -Robust Machine Scheduling with Uncertain Processing Times

Yuli Zhang (), Zuo-Jun Max Shen () and Shiji Song ()
Additional contact information
Yuli Zhang: School of Management and Economics, Be¼ing Institute of Technology, Be¼ing 100081, China
Zuo-Jun Max Shen: Department of Industrial Engineering and Operations Research, Department of Civil and Environmental Engineering, and TBSI, University of California, Berkeley, Berkeley, California 94720
Shiji Song: Department of Automation, TNList, Tsinghua University, Be¼ing 100084, China

INFORMS Journal on Computing, 2018, vol. 30, issue 4, 662-676

Abstract: 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.

Keywords: distributionally robust; β -robust scheduling; parametric search; speedup shortest augmentation path algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0807 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:4:p:662-676

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().