A weighted distribution-free model for parallel machine scheduling with uncertain job processing times

Yuli Zhang, Zihan Cheng, Ningwei Zhang and Raymond Chiong

European Journal of Operational Research, 2025, vol. 324, issue 3, 814-824

Abstract: This paper investigates a parallel machine scheduling and due date assignment problem with uncertain job processing times (JPTs) under the earliness and tardiness criteria. To mitigate the risk of over-conservative scheduling, we propose a weighted distribution-free model that considers both the worst-case and best-case expected costs when only the mean and variance of the JPTs are available. We derive the optimal weight such that the maximal regret value is minimized, and show that the optimal job assignment and sequence decisions do not rely on the weight. For identical parallel machine scheduling, we establish the optimality of an extended smallest-variance-first rule. For non-identical parallel machine scheduling, we provide an equivalent mixed 0-1 second-order conic programming reformulation and develop a two-phase approximation algorithm that integrates a greedy algorithm with a supermodularity-based random search (SRS). We show that the approximation ratio of the greedy algorithm is m, where m is the number of machines. We also provide performance guarantees for the SRS. Numerical experiments validate the effectiveness of the proposed model and demonstrate that the proposed algorithms are capable of producing near-optimal schedules.

Keywords: Parallel machine scheduling; Uncertain processing times; Distribution-free; Approximation ratios; Supermodularity (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172400969X
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:324:y:2025:i:3:p:814-824

DOI: 10.1016/j.ejor.2024.12.027

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 ().