Time-utility function
A Time/Utility Function, née Time/Value Function, specifies the application-specific utility that an action accrues depending on its completion time. TUFs and their utility interpretations, scales, and values are derived from application domain-specific subject matter knowledge. A frequent interpretation of utility is an action's relative importance, which is independent of its urgency. The traditional deadline represented as a TUF is a special case—a downward step of values from 1 to 0 at the deadline time. A TUF is more general—it has a critical time, with application-specific shapes and values on each side, after which it does not increase.
The optimality criterion for scheduling multiple TUFs historically has been solely maximal utility accrual —e.g., a sum of the individual actions' completion utilities. This thus takes timeliness with respect to critical times into account. Additional criteria, system models, scheduling algorithms, and assurances have been added as the TUF/UA paradigm and its use cases have evolved. More expressively, TUF/UA can be used in systems in which timeliness, accrued utility, and other scheduling criteria may be traded off against one another for the schedule to produce situational application QoS.
Various published examples of civilian TUF/UA applications are included in the [|References].
Time/Utility Functions
The TUF/UA paradigm was originally created to address certain timeliness- and application QoS-based scheduling needs of various military applications for which traditional real-time concepts and practices are not sufficiently expressive and resilient. An example class of such applications is ballistic missile defense.Subsequently, numerous variations on the original TUF model, the TUF/UA paradigm’s system model, and thus scheduling algorithms, have been studied in the academic literature—e.g.,—and applied in civilian contexts.
Some examples of the latter include: cyber-physical systems, AI, multi-robot systems, drone scheduling, autonomous robots, intelligent vehicle-to-cloud data transfers, industrial process control, transaction systems, high performance computing, cloud systems, heterogeneous clusters, service-oriented computing, networking and memory management. A steel mill example is briefly described in the Introduction of Clark's Ph.D. thesis. Information about any commercial or military instances of the paradigm may be publicly inaccessible.
TUFs and their utility interpretations, scales, and values are derived from domain-specific subject matter knowledge. A frequent generic interpretation of utility is actions' relative importance. A framework for á priori assigning static utility values subject to strong constraints on system models has been devised, but subsequent TUF/UA research and development have preferred to exploit application-specificity rather than attempting to create more general frameworks. However, such frameworks and tools remain an important research topic.
By convention, a TUF is a concave function, including linear ones.
TUF/UA papers in the research literature, with few exceptions, e.g., are for only either linear or piecewise linear TUFs because they are easier to specify and schedule. In many cases, the TUFs are only .
A constant TUF represents an action's utility that is not related to the action's completion time—for example, the action's relative importance. An arbitrary critical time may be chosen for the purpose of scheduling—such as the action's release time, or its TUF's terminal time. This allows both time-dependent and time-independent actions to be scheduled coherently.
A TUF has a global critical time, after which its utility does not increase. If a TUF never decreases, its global critical time is the first time when its maximum utility is reached. The global critical time may be followed by local critical times—for example, consider a TUF having a sequence of downward steps in value, perhaps to approximate a smooth downward curve.
TUF utility values usually are either integers or rational numbers.
TUF utility may include negative values.
A conventional deadline time represented as a TUF is a special case—a downward step TUF having a unit penalty.
More generally, a TUF allows downward step functions to have any pre- and post-critical time utilities.
Tardiness represented as a TUF is a special case whose non-zero utility is the linear function C - d, where C is the function's completion time—either current, expected, or currently believed. More generally, a TUF allows non-zero earliness and tardiness to be non-linear—e.g., increasing tardiness may result in non-linearly decreasing utility, such as when detecting a threat.
Thus, TUFs provide a rich generalization of traditional action completion time constraints in real-time computing. In particular, TUF-based scheduling can provide maximal timeliness with respect to critical times when the system is overloaded, superior to that of traditional scheduling approaches.
A TUF may be dynamically adapted by an application or its operational environment, independently for any actions currently either waiting or operating. These adaptations may occur either at discrete events—e.g., at an application mode change such as for ballistic missile flight phases, or continuously such as for air-to-air radar tracking where some actions’ operational durations and utilities are a function of when those actions begin operation.
Utility Accrual Scheduling
INCOMPLETE DRAFT OF WORK IN PROGRESSThis section begins by listing generic properties of TUF/UA scheduling, then summarizes a number of notable specific cases of UA research in the public literature.
Generic Properties of UA Scheduling
Multiple actions in a system may contend for access to sequentially shared resources—physical ones such as processors, networks, exogenous application devices —and logical ones such as synchronizers, data.The TUF/UA paradigm resolves each instance of this contention using an application-specific algorithmic technique which creates a schedule. The instance’s contending actions are dispatched for resource access in order from the front of the schedule. Thus, action sequencing is not greedy.
A schedule may be created offline or online. An online schedule may be either static or dynamic. An online schedule may be either pre-emptive or non-preemptive. Offline schedules are static and non-preemptive.
The algorithmic technique creates a schedule having one or more application-specific objectives.
The primary objective for scheduling actions having TUFs is maximal utility accrual. The accrued utility is an application-specific polynomial sum of the schedule’s completed actions’ utilities. When actions have one or more stochastic parameters, the accrued utility is also stochastic.