HOME

TheInfoList



OR:

A Time/Utility Function (''TUF''), née ''Time/Value Function'', specifies the application-specific ''utility'' that an ''action'' (e.g., computational task, mechanical movement) yields depending on its completion time. TUFs and their utility interpretations (semantics), scales, and values are derived from application domain-specific subject matter knowledge. An example (but not the only) interpretation of utility is an action's relative ''importance,'' which otherwise is independent of its ''timeliness''. The traditional deadline represented as a TUF is a special case—a downward step of utility from 1 to 0 at the deadline time—e.g., timeliness without importance. A TUF is more general—it has a ''critical time,'' with application-specific shapes and utility values on each side, after which it does not increase. The various researcher and practitioner definitions of ''firm'' and ''soft'' real-time can also be represented as special cases of the TUF model. The optimality criterion for
scheduling A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are ...
multiple TUF-constrained actions has historically in the literature been only maximal ''utility accrual'' (''UA'')—e.g., a (perhaps expected) weighted sum of the individual actions' completion utilities. This thus takes into account timeliness with respect to critical times. Additional criteria (e.g., energy, predictability), constraints (e.g., dependencies), system models, scheduling algorithms, and assurances have been added as the TUF/UA paradigm and its use cases have evolved. More expressively, TUF/UA allows accrued utility, timeliness, predictability, and other scheduling criteria and constraints to be traded off against one another for the schedule to yield situational ''application QoS''—as opposed to only timeliness per se. Instances of the TUF/UA paradigm have been employed in a wide variety of application domains, most frequently in military systems.


Time/Utility Functions

The TUF/UA paradigm was originally created to address certain action timeliness, predictability of timeliness, and ''application QoS''-based scheduling needs of various military applications for which traditional real-time concepts and practices are not sufficiently expressive (e.g., for dynamically timeliness-critical systems not having deadlines) and load resilience (e.g., for systems subject to routine action overloads). An important common example class of such applications is missile defense (notionally). Subsequently, numerous variations on the original TUF model, the TUF/UA paradigm's system model, and thus scheduling techniques and 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 for real and virtual machines. A steel mill example is briefly described in the Introduction of Clark's Ph.D. thesis. TUFs and their utility interpretations (semantics), scales, and values are derived from domain-specific subject matter knowledge. A historically frequent 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 (like prior) TUF/UA research and development have preferred to depend on exploiting application-specificity rather than attempting to create more general frameworks. However, such frameworks and tools remain an important research topic. By traditional convention, a TUF is a
concave function In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap, or upper convex. Definition A real-valued function f on an ...
, including linear ones. See the depiction of some example TUFs. TUF/UA papers in the research literature, with few exceptions, e.g., are for only either linear or piecewise linear (including conventional deadline-based) TUFs because they are easier to specify and schedule. In many cases, the TUFs are onl
monotonically decreasing
A
constant function In mathematics, a constant function is a function whose (output) value is the same for every input value. For example, the function is a constant function because the value of is 4 regardless of the input value (see image). Basic propertie ...
represents an action's utility that is not related to the action's completion time—for example, the action's constant relative importance. 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. A constant TUF has an arbitrary critical time for the purpose of scheduling—such as the action's release time, or the TUF's termination time. The global critical time may be followed by local critical times—for example, consider a TUF having a sequence of downward steps, perhaps to approximate a smooth downward curve. TUF utility values are usually either integers or rational numbers. TUF utility may include negative values. (A TUF that has negative values in its range is not necessarily dropped from scheduling consideration or aborted during its operation—that decision depends on the scheduling algorithm.) A conventional deadline time (''d'') represented as a TUF is a special case—a downward step TUF having a unit penalty (i.e., having utility values ''1'' before and ''0'' after its critical time). More generally, a TUF allows downward (and upward) step functions to have any pre- and post-critical time utilities.
Tardiness Tardiness is the habit of being late or delaying arrival. Being late as a form of misconduct may be formally punishable in various arrangements, such as workplace, school, etc. An opposite personality trait is punctuality. Workplace tardiness ...
represented as a TUF is a special case whose non-zero utility is the ''linear'' function ''C - d'', where ''C'' is the action's completion time—either current, expected, or 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 Real-time computing (RTC) is the computer science term for hardware and software systems subject to a "real-time constraint", for example from event to system response. Real-time programs must guarantee response within specified time constrai ...
. Alternatively, the TUF/UA paradigm can be employed to use timeliness with respect to the global critical time as a means to a utility accrual end—i.e., application-level Quality of Service (QoS)—instead of timeliness per se being an end in itself . A TUF (its shape and values) may be dynamically adapted by an application or its operational environment, independently for any actions currently either waiting or operating. These adaptations ordinarily occur at discrete events—e.g., at an application mode change such as for ballistic missile flight phases. Alternatively, these adaptations may occur continuously, such as for actions whose operational durations and TUFs are application-specific functions of when those actions are either released or begin operation. The operation durations may increase or decrease or both, and may be non-monotonic. This continuous case is called ''time-dependent scheduling''. Time-dependent scheduling was introduced for (but is not limited to) certain real-time military applications, such as radar tracking systems.


Utility Accrual Scheduling

Multiple actions in a system may contend for access to sequentially exclusively shared resources—physical ones such as processors, networks, exogenous application devices (sensors, actuators, etc.)—and logical ones such as synchronizers, data. The TUF/UA paradigm resolves each instance of this contention using an application-specific algorithmic technique that creates (or updates) a ''schedule'' at ''scheduling events''—e.g., times (such as action arrival or completion) or states. The instance's contending actions are dispatched for resource access sequentially in order from the front of the schedule. Thus, action UA sequencing is not greedy. The algorithmic technique creates a schedule based on one or more application-specific ''objectives'' (i.e., optimality criteria). The primary objective for scheduling actions having TUFs is maximal ''utility accrual'' (''UA''). The accrued utility is an application-specific polynomial sum of the schedule's completed actions' utilities. When actions have one or more stochastic parameters (e.g., operation duration), the accrued utility is also stochastic (i.e., an expected polynomial sum). Utility and accrued utility are generic, their interpretations (semantics) and scales are application-specific. An action's operation duration may be fixed and known at system configuration time. More generally, it may be either fixed or stochastic but not known (either with certainty or in expectation) until it either arrives or is released. An operation duration may be an application-specific function of the action's operation starting time—it may increase or decrease or both, and may be non-monotonic. This case is called ''time-dependent scheduling''.


Notes


References


External links


Real-Time for the Real World.

2006-2009, Systems Software Research Group, Binoy Ravindran, ECE, Virginia Tech.


* [https://www.springer.com/us/book/9783662593615?gclid=Cj0KCQjwsuP5BRCoARIsAPtX_wHOG2nAkt8eTSFJbhNa4VXlQBt_xhirlmE-ECUV5cnq8nPqgH6gpJUaAuGaEALw_wcB Stanislaw Gawiejnowicz, ''Models and Algorithms of Time-Dependent Scheduling''], 2nd ed., eBook , Springer, 2020.
Chris N. Potts and Vitaly A. Strusevich, ''Fifty Years of Scheduling: A Survey of Milestones'' (2009)

Journal of scheduling.

Multidisciplinary International Conference on Scheduling.

International Workshop on Dynamic Scheduling Problems.
{{DEFAULTSORT:Time-Utility Function Real-time computing Optimal scheduling Quality of service Software performance management