A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer

U. Waqas, M.C.W. Geilen, J. Kandelaars, L.J.A.M. Somers, T. Basten, S. Stuijk, P.G.H. Vestjens, H. Corporaal

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

7 Citations (Scopus)
10 Downloads (Pure)

Abstract

A Large Scale Printer (LSP) is a Cyber Physical System (CPS) printing thousands of sheets per day with high quality. The print requests arrive at run-time requiring online scheduling. We capture the LSP scheduling problem as online scheduling of re-entrant flowshops with sequence dependent setup times and relative due dates with makespan minimization as the scheduling criterion. Exhaustive approaches like Mixed Integer Programming can be used, but they are compute intensive and not suited for online use. We present a novel heuristic for scheduling of LSPs that on average requires 0.3 seconds per sheet to find schedules for industrial test cases. We compare the schedules to lower bounds, to schedules generated by the current scheduler and schedules generated by a modified version of the classical NEH (MNEH) heuristic [1], [2]. On average, the proposed heuristic generates schedules that are 40% shorter than the current scheduler, have an average difference of 25% compared to the estimated lower bounds and generates schedules with less than 67% of the makespan of schedules generated by the MNEH heuristic.
Original languageEnglish
Title of host publicationProceedings of the Conference on Design, Automation and Test in Europe (DATE 15) 9-13 March 2015, Grenoble, France
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages573-578
ISBN (Print)978-3-9815370-4-8
Publication statusPublished - 2015
Event18th Design, Automation and Test in Europe Conference and Exhibition (DATE 2015) - Alpexpo Congress Centre, Grenoble, France
Duration: 9 Mar 201513 Mar 2015
Conference number: 18
https://www.date-conference.com/date15/

Conference

Conference18th Design, Automation and Test in Europe Conference and Exhibition (DATE 2015)
Abbreviated titleDATE 2015
Country/TerritoryFrance
CityGrenoble
Period9/03/1513/03/15
Internet address

Fingerprint

Dive into the research topics of 'A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer'. Together they form a unique fingerprint.

Cite this