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 language | English |
|---|---|
| Title of host publication | Proceedings of the Conference on Design, Automation and Test in Europe (DATE 15) 9-13 March 2015, Grenoble, France |
| Place of Publication | Piscataway |
| Publisher | Institute of Electrical and Electronics Engineers |
| Pages | 573-578 |
| ISBN (Print) | 978-3-9815370-4-8 |
| Publication status | Published - 2015 |
| Event | 18th Design, Automation and Test in Europe Conference and Exhibition (DATE 2015) - Alpexpo Congress Centre, Grenoble, France Duration: 9 Mar 2015 → 13 Mar 2015 Conference number: 18 https://www.date-conference.com/date15/ |
Conference
| Conference | 18th Design, Automation and Test in Europe Conference and Exhibition (DATE 2015) |
|---|---|
| Abbreviated title | DATE 2015 |
| Country/Territory | France |
| City | Grenoble |
| Period | 9/03/15 → 13/03/15 |
| Internet address |