Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems

doi:10.1016/j.ejor.2022.09.032

Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems

2023-05-01

3

PRE

AI

DOI：10.1016/j.ejor.2022.09.032

Original

Original request for help

Save

Abstract

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.

Keywords:

Scheduling

Batch scheduling

Robust optimization

Shortest path problem

Polynomial -time algorithm

Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems

Abstract

Journal

Organization