Paper Info
Title
A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer
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.
Year
Venue
Keywords
2015
DATE
mixed integer programming,cyber physical system,job shop scheduling,minimisation,productivity,integer programming,schedules,flow shop scheduling
Field
DocType
ISSN
Fixed-priority pre-emptive scheduling,Job shop scheduling,Fair-share scheduling,Computer science,Parallel computing,Flow shop scheduling,Two-level scheduling,Real-time computing,Rate-monotonic scheduling,Dynamic priority scheduling,Round-robin scheduling
Conference
1530-1591
Citations 
PageRank 
References 
4
0.45
6
Authors
8
Name
Order
Citations
PageRank
Umar Waqas1102.31
Marc Geilen2134684.30
Jack Kandelaars340.45
Lou J. Somers4696.87
Twan Basten51833132.45
Sander Stuijk6107870.45
Patrick Vestjens740.45
Henk Corporaal81787166.20