Variable neighborhood search for integrated planning and scheduling

Abstract

In this paper, we consider the integrated planning and scheduling problem on parallel and identical machines. The problem is composed by two parts which are simultaneously solved in an integrated form. The first is the planning part, which consists in determining the jobs that should be processed in each period of time. The second is the scheduling part, which consists in assigning the jobs to the machines according to their release dates. We present new optimization approaches based on local search heuristics and metaheuristic methods based on variable neighborhood search using two neighborhood structures. Two different algorithms were implemented in the construction of initial solutions and combined with fifteen variants of the initial sequence of jobs. Computational experiments were performed with benchmark instances from the literature in order to assess the proposed methods.