Models, constructive heuristics, and benchmark instances for the flexible job shop scheduling problem with nonlinear routes and position-based learning

Abstract This paper addresses the flexible job shop scheduling problem with nonlinear routes and position-based learning effect. In this variant of the flexible job shop scheduling problem, precedence constraints of the operations constituting a job are given by an arbitrary directed acyclic graph, generalizing the classical case in which a total order is imposed. Additionally, it is assumed that a worker performing an operation at a machine undergoes a learning process: the more times a worker has performed an operation, the faster he or she will be able to complete it on subsequent repetitions. Mixed integer programming and constraint programming models are presented and compared in the present work. In addition, sets of benchmark instances and constructive heuristics are introduced. The problem we study here corresponds to modern problems of great relevance in the printing industry. The framework we introduce aims to assist authors in the design of novel, effective, and efficient methods. Instances with optimal solutions provide a means to evaluate the quality of solutions found by other methods. Constructive heuristics serve two purposes. First, they provide an initial solution to off-the-shelf exact methods, offering a warm start when addressing instances of the proposed models. They also lay the groundwork for developing algorithms, such as list scheduling, neighborhoods, local searches, and ultimately, metaheuristics.