A Linear Approximation Model for a Non-Linear Flow Shop Scheduling Problem with Learning Effect

Abstract

Learning effects have been considered in operations management problems since the early twentieth century [1]. The learning effect has a direct influence on production scheduling problems, since it modifies the use of production machines [2], and for this reason, it has been a problem widely studied by the scheduling community [3]. However, modeling the learning effect in scheduling problems by means of mathematical programming requires the use of non-linear expressions [4], this has limited the majority of works to be focused on single-machine problems [2] [5]. In this work, it is proposed to extend these formulations for the case that the learning effect is exponentially dependent on the previous jobs processed in the sense of [5]. This mathematical model is clearly non-linear, and by having several machines in which the learning process occurs, the probability of getting trapped in poor local optimums is very high. The proposal of this work is a linear approximation scheme, which can be implemented by a standard MIP solver such as CPLEX, in order to obtain very high quality solutions, without requiring sophisticated and tailored methods. The approximation scheme is based on a set of straight lines, which approximate the expected learning effect, generating a convex shell to the problem with expected values, thus avoiding falling into poor quality local optimal points. For creating the convex shell, a least-squares problem must be solved, which is also non-linear, but does not require integer variables, then, it can be solved by simple solvers like the ones provided by spreadsheet software. To evaluate the capability of the solution scheme, the proposed linear model solution was compared with the solution obtained by a proven MINLP solver such as DICOPT [6], in flow shop problems with makespan as the objective function. The results show that the proposed scheme notably improves the solutions obtained by DICOPT, reducing the makespan in up to 12%.