Planning and scheduling approaches in real manufacturing environments entail the need to cope with random attributes and variables to match the characteristics of real scheduling problems where uncertain events are frequent. Moreover, the capability of devising robust schedules, which are less sensitive to the disruptive effects of unexpected events, is a major request in real applications. In this paper, a branch-and-bound approach is proposed to solve the two-machine permutation flow shop scheduling problem with stochastic processing times. The objective is the minimisation of the value-at-risk of the makespan, to support decision-makers in the trade-off between the expected performance and the mitigation of the impact of extreme scenarios. A Markovian Activity Network (MAN) model is adopted to estimate the distribution of the makespan and assess the value-at-risk for both partial and complete schedules. Phase-type distributions are used to enable general distributions for processing times while maintaining the capability to exploit a Markovian approach. The effectiveness and performance of the proposed approach are demonstrated through a set of computational experiments.

A branch-and-bound approach to minimise the value-at-risk of the makespan in a stochastic two-machine flow shop

Liu L.;Urgo M.
2024-01-01

Abstract

Planning and scheduling approaches in real manufacturing environments entail the need to cope with random attributes and variables to match the characteristics of real scheduling problems where uncertain events are frequent. Moreover, the capability of devising robust schedules, which are less sensitive to the disruptive effects of unexpected events, is a major request in real applications. In this paper, a branch-and-bound approach is proposed to solve the two-machine permutation flow shop scheduling problem with stochastic processing times. The objective is the minimisation of the value-at-risk of the makespan, to support decision-makers in the trade-off between the expected performance and the mitigation of the impact of extreme scenarios. A Markovian Activity Network (MAN) model is adopted to estimate the distribution of the makespan and assess the value-at-risk for both partial and complete schedules. Phase-type distributions are used to enable general distributions for processing times while maintaining the capability to exploit a Markovian approach. The effectiveness and performance of the proposed approach are demonstrated through a set of computational experiments.
2024
Flow shop
Markovian activity networks
phase-type
stochastic scheduling
value-at-risk
File in questo prodotto:
File Dimensione Formato  
A branch-and-bound approach to minimise the value-at-risk of the makespan in a stochastic two-machine flow shop.pdf

Accesso riservato

: Publisher’s version
Dimensione 2.22 MB
Formato Adobe PDF
2.22 MB Adobe PDF   Visualizza/Apri
0A branch-and-bound approach to minimise the value-at-risk of the makespan in a stochastic two-machine flow shop.pdf

Open Access dal 28/05/2024

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 715.34 kB
Formato Adobe PDF
715.34 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1240297
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact