Robust scheduling in a two-machine re-entrant flow shop to minimise the value-at-risk of the makespan: branch-and-bound and heuristic algorithms based on Markovian activity networks and phase-type distributions

Lei Liu () and Marcello Urgo ()
Additional contact information
Lei Liu: University of Nottingham
Marcello Urgo: Politecnico di Milano

Annals of Operations Research, 2024, vol. 338, issue 1, No 26, 764 pages

Abstract: Abstract This paper addresses a two-machine re-entrant flow shop scheduling problem with stochastic processing times where each job is expected to require a rework phase, flowing twice within the whole system. Due to the stochastic characteristics of the addressed problem, the proposed approach aims to devise robust schedules, i.e., schedules that are less sensitive to the occurrence of uncertain events, specifically, to the variability of the processing times. Two classes of approaches are proposed: the first is a branch-and-bound algorithm capable of solving the problem optimally, although with limitations regarding the size of the scheduling instances; the second is heuristic algorithms that can be applied to medium/large instances. For both approaches, the goal is to minimise the value-at-risk associated with the makespan, to assist decision-makers in balancing expected performance and mitigating the impact of extreme scenarios. A Markovian Activity Network (MAN) model is exploited to estimate the distribution of the makespan and evaluate its value-at-risk. Phase-type distributions are used to cope with general distributions for the processing times while exploiting a Markovian approach. A set of computational experiments is conducted to demonstrate the effectiveness and performance of the proposed approaches.

Keywords: Flow shop; Stochastic scheduling; Re-entrant flow shop; Markovian activity networks; Risk measure (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-05647-1 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-05647-1

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

DOI: 10.1007/s10479-023-05647-1

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 ().