Two-level priority scheduling framework in a max-plus linear representation

Abstract

A common type of scheduling policy includes first-in-first-out (FIFO) and earliest-outset bases. Among many approaches to this, max-plus linear representation is beneficial for event-driven discrete event systems (DESs). The earliest event occurrence times can be represented by linear relations in max-plus algebra, the resultant of which is analogous with the state equation in modern control theory. Methodologies in control theory such as evolution prediction and just-in-time scheduling can thus be utilized. Although useful, the description capability remains confined to FIFO contexts, for which the method would not be capable of producing an efficient solution for systems with two-level priorities. An entity, e.g. a task or token in scheduling contexts, with higher qualification would be prioritized over one with a lower qualification. A framework for overtaking tasks is necessary for this. Motivated by this need, this article is concerned with constructing a two-level priority scheduling methodology in a max-plus linear context. A numerical experiment applied to a simple manufacturing system highlights the significance of the constructed method.

Keywords

• max-plus linear
• state equation
• first-in first-out
• two-level priority scheduling
• prioritization