A DC OPTIMIZATION FORMULATION FOR THE FLOW SHOP PERMUTATION PROBLEM

This study applies global optimization theory based on Difference of Convex functions (DC programming) to solve the Permutation Flow Shop Scheduling Problem (PFSSP), which seeks to determine the processing sequence of jobs that minimizes the completion time of the last job (makespan). The integrality constraints of the PFSSP can be expressed as the difference of two convex functions, allowing the problem to be reformulated in the canonical form of a DC program. This reformulation makes it possible to identify global solutions under certain theoretical conditions. The model proposed by Wilson [Stafford et al., 2005]
is adopted and reformulated in this work as a locally convex problem with linear equality constraints. An interior-point method is implemented to solve it. The optimality conditions of DC theory are explored for the PFSSP for the first time. Computational results validate the effectiveness of the proposed methodology.