A reduced variable neighborhood search for the just in time job shop scheduling problem with sequence dependent setup times
Paolo Brandimarte, Edoardo Fadda
Abstract
In this paper, we deal with the just-in-time job shop scheduling problem with sequence-dependent setup times and release dates. Given a set of jobs characterized by release and due dates, the goal is to execute them by minimizing a weighted sum of their earliness, tardiness, and flow time (i.e., the difference between completion and start time of each job). We develop new destroy and repair operators by exploiting the structure of the problem, and we use them within a reduced variable neighborhood search matheuristic. Computational experiments carried out on several sets of instances show that the proposed algorithm outperforms existing solution methods.
Topics & Concepts
Variable neighborhood searchJob shop schedulingComputer scienceSequence (biology)Scheduling (production processes)Flow shop schedulingMathematical optimizationVariable (mathematics)MathematicsMetaheuristicScheduleGeneticsMathematical analysisBiologyOperating systemScheduling and Optimization AlgorithmsAdvanced Manufacturing and Logistics OptimizationOptimization and Search Problems