Online Scheduling for Reprographic Machines
Markus P. J. Fromherz, Lise Getoor, Duplex Loop · 1997
Introduction We present a real-world online scheduling application. In this application, the problem input is fed incrementally to the scheduler, and the scheduler has only a portion of the entire job available before it has to start making scheduling decisions. In fact, job submission, scheduling and execution may all happen in parallel and at different speeds. We are investigating constraint-based online scheduling inthe domain of reprographic machines (photo-copiers, printers, and fax machines). The task of a generic reprographic ma hine scheduler isto schedule the operations that produce a given document in real-time. In particular, we focus on optimizing the make-span ofthe schedule, i.e., minimizing the output time of the last sheet. The make-span isusually taken as a measure of a machine’s productivity. Forhigh-end machines, productivity improvement often translates proportionally to an increase in perceived value. For expensive machines, even small improvements (e.g., by 5-10%) are significant. Constraint programming (Van Hentenryck 1989) and the large body of experience with constraint-based scheduling (Zweben & Fox 1994) provide a well-suited foundation for online scheduling. However, optimizing overall productivity s difficult inan online nvironment, and even more so with a real-time algorithm. Not only is it difficult to choose the right schedule without complete job information, but there may not even be enough time to find that schedule. This has motivated our work on heuristics for online scheduling (Getoor et al. 1997). Here, we point out further research directions in this area.