Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches

We consider modeling the reentrant job shop scheduling problem with sequence dependent setup times in the context of metaheuristic search methods. We begin by investigating feasibility conditions when sequence dependent setups are incorporated into the traditional job shop scheduling problem. The investigation reveals that traditional methods of avoiding infeasible solutions for iterative search techniques do not suffice. The conditions under which these infeasible solutions occur are presented and an algorithm is presented to remove such infeasibilities. Reentrancy and its relationship to the traditional model are then illustrated, and the new features of the disjunctive graph are introduced. We conclude with a simple algorithm for obtaining an initial feasible solution, benefits of this research, and an application to the reentrant job shop scheduling problem with sequence dependent setups.