The scheduling algorithm of the printer is an important factor that affects printing efficiency. For current printers, paper scheduling often follows the first-in-first-out principle, so it is often not optimal. The printer system is a type of semi-cyclic discrete-event system with synchronization but no concurrency. The system contains a set of operations that vary over a limited sequence of operations, which can be further modelled as a Switching Max-Plus-Linear (SMPL) system through max-plus-linear algebra, and can be switched between different modes of operation. Since max-plus algebra has a significant analogy with conventional algebra, some properties in conventional algebra can be applied to such kind of system, making the system easier to achieve optimal control.

In this report, a printing scheduler modelled by the max-plus algebra is presented. We review and summarize the basic knowledge of the Max-Plus-Linear (MPL) system from the existing literature in the first half of the report. We first introduce the basic properties of max-plus algebra and SMPL systems. Then we turn to the stochastic case, and consider the two types of stochastic uncertainty that may be included in the SMPL system, namely stochastic parametric uncertainty and stochastic mode switching uncertainty. Next, we review a Model Predictive Control (MPC) approach that can achieve optimal scheduling of systems containing two random uncertainties.

In the second half of the report, based on the content summarized in the first half, we make a further derivation of the printer scheduling system modelled by SMPL approach. We first present the modelling framework of the printer. Three working modes, namely duplex mode, idle mode and simplex mode, are modelled separately and merged into a compact form. Then a scheduler that takes the feeding and processing time of each sheet of paper as design variables is introduced. It can find the global optimal schedule of different types of paper by solving the Mixed-Integer Linear Programming (MILP) problem. After that, we discuss cases involving switching, and consider switching between two sizes of paper and two working modes. Three possible intermediate switching modes are designed. Finally, we take noise/interference into consideration, discuss the impact of noise on scheduling, and the changes that the previously proposed methods may require to achieve optimal scheduling in the presence of noise.