Single machine scheduling with release dates: A distributionally robust approach

Haimin Lu and Zhi Pei

European Journal of Operational Research, 2023, vol. 308, issue 1, 19-37

Abstract: In the present study, a single machine scheduling problem with job release dates is considered, where the job processing time is depicted by an ambiguity set, with the mean, the mean absolute deviation, and the support set information given. To the best of our knowledge, this is the first time that a distributionally robust optimization method is applied to the single machine scheduling with release dates. Based on the risk attitude of the decision maker, two distributionally robust optimization models are proposed, namely, the risk-neutral and risk-averse scheduling. The two models concern with the worst-case performance and the robust conditional value-at-risk with respect to the total flow time, respectively. Since the proposed robust optimization models are intractable in nature, we reformulate them as two separate mixed-integer linear programming models, which can then be solved via off-the-shelf solvers. Interestingly, it is proved that the mean absolute deviation can be ignored in the risk-neutral robust model. Thus a more succinct reformulation is constructed, which can be rapidly solved to optimum. Furthermore, extensive numerical experiments are performed with the stochastic programming model as a benchmark. And it is observed that the risk-averse model outperforms the others on both the average and worst-case metrics in most cases. Meanwhile, the risk-neutral model is more preferable on the average metric when the jobs are sparsely released.

Keywords: Scheduling; Release date; Distributionally robust optimization; CVaR; Mixed-integer linear programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172200861X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:308:y:2023:i:1:p:19-37

DOI: 10.1016/j.ejor.2022.11.005

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().