Otimização por colônia de formigas para o problema de programação job-shop flexível multiobjetivo

Abstract

The job-shop production scheduling activity is at the most detailed and complex level of a production planning and control system. The Flexible Job-shop Scheduling Problem (FJSP) is an extension of the job-shop scheduling problem (JSP) and plays an important role in because of its combinatorial nature that allows an operation to be processed in more than one alternative machine of the set of available resources. Problems of job-shop programming belong to the class of NP-complete problems due to the difficulty in obtaining an optimal solution by traditional approaches. The metaheuristic Ant Colony Optimization (ACO) has proved to be efficient in solving combinatorial optimization problems. The ACO consists of an algorithm inspired by the behavior of the ant colonies, which functions as a probabilistic method and constructs solutions through collective intelligence. In this way, it uses the experience gained during the search process adaptively. In this work an Ant System (AS) is presented along with the Shortest Processing Time (SPT) rule for multiobjective FJSP resolution. Traditionally, allocation and scheduling decisions are made separately in production management. Thus, the proposed approach employs the SPT rule for resource allocation and the AS algorithm for the sequencing of assigned operations, where each ant constructs a viable scheduling according to the constraints that apply to the problem. The objective of this research is to find optimal solutions for the FJSP, considering minimization of completion time, minimization of the most critical machine load and minimization of the total load of all machines as optimization criteria. The combination of several optimization criteria induces additional complexity and new problems. However, the results of the comparative study with other approaches in instances known in the literature have shown that the proposed algorithm is feasible and effective for solving multiobjective FJSP, especially in large scale problems.