A review of the static stochastic flow-shop scheduling problem

Abstract

We consider a m machine stochastic flow-shop and a set of n jobs, with known release dates, to be processed. In this paper, we distinguish two types of random events: processing times (job processing times are random variables which follow a probability distribution function) and breakdowns (time between failure and repair time are random variables). The main purpose of this paper is to review and to propose a classification for some developments about the static stochastic flow-shop scheduling problem. We propose also an extension of the notation of Graham, Lawler, Lenstra, and Rinnooy Kan in order to take into account random events.

Nous considérons un flow-shop stochastique, composé de m machines et un ensemble de n produits à traiter. Les dates de disponibilité des produits sont connues. Dans cet article, nous distinguons deux types d'événements aléatoires : les temps de traitement (les temps de traitement des produits sont des variables aléatoires qui suivent une fonction de distribution de probabilité) et les pannes (les durées inter pannes et les durées de réparation sont des variables aléatoires). L'objectif de cet article est de donner un état de l'art et de proposer une classification des travaux existants sur le problème d'ordonnancement du flow-shop statique stochastique. Nous proposons également une extension de la notation de Graham, Lawler, Lenstra, and Rinnooy Kan pour tenir compte des événements aléatoires.

Keywords:

• Flow-shop
• Stochastic
• Scheduling
• Breakdowns
• Random processing times

Mots clés:

• Flow-Shop
• Stochastique
• Ordonnancement
• Pannes
• Temps de traitement aléatoires