A distributionally robust approach for the two-machine permutation flow shop scheduling

Haimin Lu () and Zhi Pei ()
Additional contact information
Haimin Lu: Zhejiang University of Technology
Zhi Pei: Zhejiang University of Technology

Annals of Operations Research, 2024, vol. 338, issue 1, No 25, 709-739

Abstract: Abstract We consider the two-machine permutation flow shop scheduling problem with uncertain job processing time, which is sampled from no specific distribution type. For the ease of discussion, an ambiguity set with a priori mean and support set information is constructed. We then introduce a distributionally robust optimization (DRO) perspective to handle the uncertainty. To the best of our knowledge, this is the first time that a DRO method is applied to this problem setting. Given that the original DRO model is nonlinear and intractable in nature, we first reformulate the inner maximization problem into a linear programming model with a fixed sequence, based on the duality theory and optimality conditions. By including the sequence decision, we further transform it into an equivalent mixed-integer linear programming (MILP) problem via incorporating the valid lower and upper bounds and McCormick inequalities. The obtained MILP could be solved to optimality with the off-the-shelf commercial solvers. In the numerical study, it is demonstrated that the DRO-based model could effectively solve the large scale instances with up to 100 jobs optimally within 30 s. Compared with the SLP, DRO model always triumphs on the worst-case indicator. And as the problem scale increases, the DRO model gradually outperforms the SLP in terms of the Up-90% and Up-75% indicators. Furthermore, the optimal sequence obtained by the deterministic model is less stable than the DRO model, which can enhance the robustness of the manufacturing system against processing uncertainty.

Keywords: Scheduling; Flow shop; Distributionally robust optimization; Mixed-integer linear programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-023-05489-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:338:y:2024:i:1:d:10.1007_s10479-023-05489-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-023-05489-x

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().