Skip to Main content Skip to Navigation
Journal articles

Robust (min–max regret) single machine scheduling with interval processing times and total tardiness criterion

Abstract : This paper studies a robust (min–max regret) single machine scheduling problem with uncertain processing times represented by interval data. The objective is to obtain robust sequences of jobs that minimize the absolute deviation of total tardiness from the optimal solution under the worst-case scenario. The problem is first formulated as a mixed-integer linear programming (MILP) model and assuming that the corresponding deterministic NP-hard problem for the mid-point scenario can be solved optimally, an optimal schedule under the mid-point scenario is then proved to be a 2-approximation solution to the problem. Next, the worst-case scenarios are proved to be not necessarily at the upper or lower limits of the interval processing times. Utilizing these results, a 2-approximation algorithm (2AA), a worst-case scenario-based heuristic (WSH), and an approximate worst-case-based heuristic (AWH) are proposed and empirically evaluated, in which an iterative procedure for evaluating the maximum regret of a solution is integrated. Finally, the paper is concluded by suggesting some fruitful directions for future research in this area.
Document type :
Journal articles
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02943333
Contributor : Frédéric Davesne <>
Submitted on : Friday, September 18, 2020 - 11:09:05 PM
Last modification on : Wednesday, October 14, 2020 - 4:21:43 AM

Identifiers

Citation

Shijin Wang, Wenli Cui, Feng Chu, Jianbo Yu, Jatinder N.D. Gupta. Robust (min–max regret) single machine scheduling with interval processing times and total tardiness criterion. Computers & Industrial Engineering, 2020, 149, pp.106838. ⟨10.1016/j.cie.2020.106838⟩. ⟨hal-02943333⟩

Share

Metrics

Record views

38