Flow shop scheduling problem with non-linear learning effects: A linear approximation scheme for non-technical users

Abstract

Scheduling problems with learning effect have taken a renewed interest in recent years due to increasingly personalized productions, leveraged by the capabilities provided by Industry 4.0. In this work, a learning effect problem described by an exponential curve proportional to the accumulated processing time in a flow shop type configuration was addressed. The objective to be minimized is the makespan. This problem is non-linear, which prevents it from being addressed by standard software such as spreadsheets and commercial MILP solvers. For overcoming this issue a linear approximation approach is proposed. This linear approximation approach consists in representing the exponential curve by a set of piecewise smooth lines. The parameterization of the piecewise smooth line can be solved with spreadsheet tools, using probabilistic models that implicitly provide information about the difficulty of modeling an exponential curve by means of straight lines. Then, a MILP model was generated based on this approximation scheme, which can be solved by standard solvers such as CPLEX or Gurobi. In turn, the problem was also modeled in its MINLP format, and it was solved with a state-of-the-art MINLP solver. The results show the improvement of the linear approximation solution with respect to the MINLP solution, where improvements greater than 10% are achieved in terms of makespan.