.png){kind=icon}
返回
Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2022.09.032.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We study robust single-machine batch scheduling problems under uncertain processing times to min-imize total flow time. Two types of batches are considered: serial batch (s-batch) and parallel batch (p-batch). These problems can model many on-site production and logistics applications which involve uncertain factors such as defect rates. We first prove that a sequencing rule for the shortest nominal processing time is optimal for both s-batch and p-batch problems. We then propose polynomial-time algorithms based on the observation that the robust batch scheduling problems are reducible or par-tially reducible to a constrained shortest path problem through worst-case scenario analysis. We further present more efficient algorithms for the special case of uniform maximum deviation times for all jobs. The algorithms are evaluated computationally, and the results show that their performance is satisfactory on the tested instances. (c) 2022 Elsevier B.V. All rights reserved.
Keyword:
Scheduling
Batch scheduling
Robust optimization
Shortest path problem
Polynomial -time algorithm
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容