数学优化
调度(生产过程)
计算
启发式
线性规划
整数规划
计算机科学
灵敏度(控制系统)
作业车间调度
集合(抽象数据类型)
稳健优化
算法
数学
地铁列车时刻表
工程类
操作系统
电子工程
程序设计语言
作者
Yuanbo Li,Yong-Hong Kuo,Runjie Li,Houcai Shen,Lianmin Zhang
标识
DOI:10.1080/00207543.2022.2053602
摘要
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.
科研通智能强力驱动
Strongly Powered by AbleSci AI