Makespan service level for the flexible job-shop scheduling problem under machine-related uncertainty

The stochastic flexible job-shop scheduling problem with random processing times is considered in this paper, where the makespan service level is maximized, i.e., the probability that a schedule is completed before a given deadline. In practice, this deadline corresponds to the scheduling horizon (e.g., a shift, a day or a week) during which the set of jobs to schedule must be completed. Compared to previous research, the uncertainty is related to the machine and the processing times of all operations processed on a machine are similarly impacted by the machine status. This helps to propose a new way of generating scenarios and deal with uncertainty. New bounds on the makespan service level are also proposed, and included in a tabu search approach. Computational experiments are conducted, that illustrate the relevance of the proposed approach. Several perspectives are proposed in the conclusions of the paper.