Markovian analysis for performance evaluation and scheduling in m machine stochastic flow-shop with buffers of any capacity

This paper deals with performance evaluation and scheduling in m machine static stochastic permutation flow-shop with buffers of any capacity (unlimited, limited or null). The processing time of a given job for a given machine is assumed to be exponentially distributed with a known rate. We propose a theorem which provides recursive scheme based on Markov chains and Chapman-Kolmogorov equations to compute the expected completion time of the last job for any sequence of jobs. This scheme is combined with metaheuristics based on simulated annealing for the scheduling problem. Computational results are given.