Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

This paper presents an arc flow model for the job scheduling problem on parallel machines to minimize the total time to process all jobs on the most loaded machine (makespan). In the proposed model, the objective function minimizes the largest value associated with a vertex where the initial flow is injected into the network. To make this approach consistent, the origin of the flow occurs at nodes related to the interval between the lower and upper bounds. This approach implies reversing the flow direction, making node zero the final destination, unlike the conventional approach where node zero is the origin of flow. We tested the model using CPLEX v20.1 to solve 3500 instances, considering different ratios between the number of jobs and machines. The computational results showed that obtaining optimal solutions with an average percentage time gain of 400% compared to the literature model was possible.