A Two‐Level Metaheuristic Algorithm for the Job‐Shop Scheduling Problem

This paper proposes a novel two‐level metaheuristic algorithm, consisting of an upper‐level algorithm and a lower‐level algorithm, for the job‐shop scheduling problem (JSP). The upper‐level algorithm is a novel population‐based algorithm developed to be a parameter controller for the lower‐level algorithm, while the lower‐level algorithm is a local search algorithm searching for an optimal schedule in the solution space of parameterized‐active schedules. The lower‐level algorithm’s parameters controlled by the upper‐level algorithm consist of the maximum allowed length of idle time, the scheduling direction, the perturbation method to generate an initial solution, and the neighborhood structure. The proposed two‐level metaheuristic algorithm, as the combination of the upper‐level algorithm and the lower‐level algorithm, thus can adapt itself for every single JSP instance.