A target-based distributionally robust model for the parallel machine scheduling problem

Yuanbo Li, Yong-Hong Kuo, Runjie Li, Houcai Shen and Lianmin Zhang

International Journal of Production Research, 2022, vol. 60, issue 22, 6728-6749

Abstract: We develop a distributionally robust optimisation (DRO) model based on a risk measure for the parallel machine scheduling problem (PMSP) with random job processing times. We propose an underperformance risk index (URI) to control the extent of the total weighted completion time (TWCT) that exceeds target level T. With partially characterised uncertainty set information, we transform the model with URI to its equivalent mixed-integer linear programming (MILP) counterparts. Due to the NP-hardness of PMSP with different job weights, we design a hybrid algorithm with a heuristic assignment and exact subproblem for large-scale problems. The proposed hybrid algorithm reduces the computation time significantly at the expense of solution quality. We also introduce a reformulation approach under the setting of equally weighted and identical machines. Numerical results show that our model performs better than the distributionally β-robust optimisation models. Our proposed URI accounts for both the frequency and magnitude of violation from the target. The uncertainty set we used preserves a linear structure under partially characterised distributional information. Our computational results and sensitivity analysis show the effectiveness and efficiency of our proposed DRO model under various settings, including different problem sizes, different processing time variations, and information misalignment.

Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2022.2053602 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:60:y:2022:i:22:p:6728-6749

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2022.2053602

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().