Track: Operations Research

Abstract

A discrete event system (DES) changes the internal states at discrete time instants according to event occurrences. Regular systems have a structure of parallelization and synchronization of multiple events. In formulating a scheduling problem in a DES context, the earliest event occurrence time is described by the ‘max’ and addition operations. These operations correspond to the synchronization and time elapse of events, which are respectively represented by addition and multiplication in max-plus algebra. The time instant of earliest event occurrence is associated with the earliest completion time in the program evaluation and review technique (PERT) context. The max-plus linear (MPL) representation described in max-plus algebra is beneficial in dealing with formulation of scheduling problems in PERT.

On the other hand, the max-min-plus scaling system (MMPS), an extended formalization of max-plus algebra, provides a richer descriptive capability than that of MPL systems have. This involves the ‘min’ operation, in addition to the ‘max’ and addition operations. The ‘min’ operation represents selection of events applied to scheduling problems. In contrast to the MPL representation, however, it has been hard to obtain an explicit solution in the max-min-plus (MMP) equation, where a scheduling problem on MMPS can be confined to an MMP equation.

In this study, we focus on a scheduling problem with a directed acyclic graph (DAG)-structured network. The aim is to develop a framework for solving MMP equations. Since a DAG is acyclic, an MMP equation associated with the earliest completion time has constantly a solution. Thus, an MMP equation could be solved directly through formula manipulation using a computer; some algebraic expressions might aid representing efficiently the relevant operations along with associated parameters. With the constructed framework, MMP equations can be solved in a straightforward manner, even for large-scale systems for which the resulting formula would be intractable in dealing with it manually.