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

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.