|
doi: 10.7873/DATE.2015.0519
A Re-entrant Flowshop Heuristic for Online Scheduling of the Paper Path in a Large Scale Printer
Umar Waqas1,a, Marc Geilen1, Jack Kandelaars2, Lou Somers2, Twan Basten1, Sander Stuijk1, Patrick Vestjens2 and Henk Corporaal1
1Department of Electrical Engineering, Eindhoven University of Technology, Eindhoven, The Netherlands.
au.waqas@tue.nl
2Research and Development, Océ Technologies, Venlo, The Netherlands
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 reentrant 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.
Full Text (PDF)
|