A Heuristic for Variable Re-Entrant Scheduling Problems

Flexible Manufacturing Systems (FMSs) need a scheduler to provide timing instructions for the operations of different products. Previous work has presented heuristics for fixed-order 2-re-entrant scheduling problems; where products visit a re-entrant machine exactly two times for production. We propose an extension to this scheduling model, and an extension to the scheduling heuristic, that allows jobs to move along different flows on re-entrant machines; i.e. jobs can visit the re-entrant machine once or twice. An FMS that requires such variable re-entrance with fixed-order output is a Large Scale Printer (LSP). The scheduling problem in an LSP is modeled as a variable re-entrance flowshop with relative due dates and sequence-dependent setup times, with a fixed order output. We show that out-of-order input of products can be beneficial to the scheduling quality in variable re-entrance scheduling. A fixed re-entrant heuristic is extended such that it orders operations on the re-entrant machine to minimize the completion time of variable re-entrant job sets. The resulting heuristic produces good quality schedules for variable re-entrant job sets without losing schedule quality for fixed re-entrant job sets.