Flexible job shop scheduling problem with non-linear routes, energy awareness and position-based learning effect

Resumo

The flexible job shop scheduling problem is notable for its many practical applications, such as in the on-demand printing industry, glass industry, steel production planning, and automotive repair shops. Additionally, sustainability has become one of the main objectives across all human activities, particularly in production environments. This work we consider the flexible job shop scheduling problem with the objective of minimizing energy consumption. As it is known that a considerable part of the energy consumption occurs when the machines are on and idle, the addressed problem includes the possibility of turning the machines off and on between processing operations. To bring the problem closer to the large variety of real-world problems it encompasses, we include two relevant factors: nonlinear routes and position-based learning effect. The treated problem is formally described through a mixed integer linear programming model. We propose constructive heuristics and two types of neighborhood with which we construct local search schemes. The local search strategies both modify solutions by removing and reinserting operations, but in different ways. The first, called SRRN (Single-Operation Removal and Reinsertion Neighborhood), removes and reinserts a single operation in a position that avoids forming cycles. The second, called SRDRRN (Single-Operation Removal, Destruction, Reinsertion, and Reconstruction Neighborhood), removes an operation along with its successors. If it is reinserted elsewhere, the new position’s operation and its successors are also removed. The resulting partial solution is then rebuilt using the proposed constructive heuristic. In addition, three meta-heuristics – namely, variable neighborhood search, greedy adaptive search procedure, and simulated annealing – have been tailored for the problem at hand. We conduct a large number of experiments to evaluate the performance of the introduced methods, on small-sized and large-sized instances. In the large-sized instances, the general variable neighborhood search, that combines the two neighborhoods into a single method, is particularly effective. In the small-sized instances with known optimal solution, the greedy randomized adaptive search procedure finds solutions that, on average, are within 0.22% of the optimal solution. The instances evaluated in this work are all available at http://www.ime.usp.br/∼egbirgin/ for future comparisons.