Modelo de arranjo linear e desigualdades válidas para o problema job shop com minimização do makespan

Abstract

The job-shop scheduling problem (JSSP) consists in scheduling n jobs on m machines. Each job has a processing order on the machines, it can even be a specific order for each one, and a processing time on each one. In addition, each job cannot be processed at the same time on two different machines, each machine cannot process two jobs at the same time, and if a job started processing on one machine, then this processing will be completed without interruptions. One of the objective functions for this problem is to minimize the completion of the last job processed, also known as makespan. Thus, for this objective function, the problem is NP-Hard for at least three machines and two jobs and, for this problem, the computational effort can be huge to solve the problem in real instances. Therefore, it is important to develop new models to achieve more efficient results, both in terms of the execution time and the quality of the problem solutions. For that, we explored the model of Andrade et al. (2017) for the minimal linear arrangement (MinLA) problem and we adapted the model for MinLA to develop a new model for JSSP, called (MLJ). In a complementary way, we explore the structure of the problem solution to develop new valid inequalities for JSSP based on the accumulated processing time a priori and a posteriori of the execution of a job on a given machine. We apply these inequalities for the models of Manne (1960), Liao and You (1992) and (MLJ), named of (M2),(L2) e (MLJ2), respectively, and tested them on benchmark instances from the literature and for a new set of instances. Based on the computational experiments, when we compare the models with valid inequalities to the original models, we obtain an improvement in the linear relaxation of (M2) and (L2) for the new instances by about 87% and we obtained gaps as good as or better in 50% of them for the model (M2) and about 67% of them for the model (L2). In addition, we improved the linear relaxation of (M2) in about 84% of the instances from the literature and achieved gaps as good as or better in 80% of them. Finally, we found that the model (MLJ2) had a similar behavior of model (M2).