An Application of the Piecewise Linear Approximation Method to Solve the β-Robust Scheduling Problem in a Parallel Machine Environment (#705)

Authors

Fernández Pérez, Miguel Angel

Abstract

In the industries, the presence of uncertainties in the duration of production tasks can lead to unsatisfactory production scheduling, in situations where variability is significant, and a deterministic approach is used. In this case, a stochastic or robust approach is more appropriate. In particular, this article deals with the β-robust scheduling problem in a parallel machine environment and considering the presence of uncertainty in the duration of the tasks. This problem consists of finding the execution order of a set of tasks on a set of machines, with the objective of maximizing the probability that the total flow time is less than a limit. The difficulty in solving this problem lies in its combinatorial, stochastic and non-linear nature of its formulation. To overcome this difficulty, an efficient mathematical model is built that makes use of the piecewise linear approximation method. The proposed model proves to be able to obtain the solution of the problem with precision and in a short computational time.