Un Squirrel Search Algorithm discreto aplicado al problema Job Shop con operadores calificados

Abstract

Introduction: The Job Shop problem With Skilled Operators (JSSO) is an extension of the classic Job Shop in which, an operation must be executed by a limited set of workers, aiming to minimize jobs total termination time or Makespan. This situation can represent different applications in daily life. JSSO is a complex problem and its classified as NP-HARD..

Objective: In this article, the JSSO problem is addressed. It is made by adapting an algorithm known as Squirrel Search Algorithm (SSA).

Method:  A discrete encoding scheme is proposed for the SSA algorithm and the Smallest Position Value (SPV) method are used. Also, solutions that can violate the precedent relationships are corrected with the Valid Particle Generator (VPG) method, which guarantees feasible solutions. Two versions of the algorithm were tested in 28 instances proposed in the literature to valid their performance.

Results: Computer experiments show that the proposed algorithms reach optimal solutions in 25 and 28 analyzed instances. In addition, for the instances where optimality was not achieved, the average gap does not exceed the 2% for both versions of the proposed algorithms.

Conclusions: The proposed encoding scheme guarantees the discretization of the algorithms, generating solutions that converge towards the optimum. In addition, the proposed encoding allows natural use of movement operators originally proposed for the algorithms used. Performance obtained by the algorithms is adequate and of high quality.