The Stochastic Flexible Job-shop Scheduling Problem (SFJSP) is an extension of the FJSP, in which a set of jobs have to be processed on a set of flexible machines, and each job requires a number of consecutive operations (routing) before being completed. Finding a solution to this problem means determining both an assignment of operations to machines and a sequence of the operations on the machines while respecting the routing of every job.

The SFJSP has been considerably less studied than its deterministic version. In the FJSP, all problem parameters are supposed to be known, and set-up times between operations are negligible or included in the processing times. In the SFJSP considered in this work, processing times are considered stochastic and characterized by independent random variables following known finite probability distributions. Under random processing times and for a given threshold T, the probability that the makespan is lower than or equal to T is maximized. To solve the SFJSP with makespan service level, a solution approach, based on tabu search and a Monte Carlo sampling-based approximation dedicated to considering random processing times, is introduced in our previous work.

In this abstract, we extend the notion of service level to other regular criteria. We also apply a new approach to deal with random processing times in the FJSP, by operating directly with the probability distributions of processing times and exploiting several bounds of the probability distribution associated with the considered optimization criterion.