A heuristic for variable re-entrant scheduling problems

Roel van der Tempel, Joost van Pinxten, Marc Geilen, Umar Waqas

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings - 21st Euromicro Conference on Digital System Design, DSD 2018
EditorsNikos Konofaos, Martin Novotny, Amund Skavhaug
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Number of pages6
ISBN (Electronic)978-1-5386-7377-5
Publication statusPublished - 12 Oct 2018
Event21st Euromicro Conference on Digital System Design, DSD 2018 - Prague, Czech Republic
Duration: 29 Aug 201831 Aug 2018
Conference number: 21


Conference21st Euromicro Conference on Digital System Design, DSD 2018
Abbreviated titleDSD 2018
Country/TerritoryCzech Republic
Internet address


  • Flexible Manufacturing Systems
  • Re entrant flowshops
  • Scheduling Optimization
  • Variable re entrancy


Dive into the research topics of 'A heuristic for variable re-entrant scheduling problems'. Together they form a unique fingerprint.

Cite this