imported>BD2412: Clean up spacing around commas and other punctuation fixes, replaced: ,A → , A, ,c → , c

2025-03-19T02:28:12Z

Clean up spacing around commas and other punctuation fixes, replaced: ,A → , A, ,c → , c

New page

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.<ref name="Jensen+ 85" /><ref name="Jensen 93" /> 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. [[File:TUFs1 color 150% trimmed.png|thumb|Depiction of Example TUFs]]

The optimality criterion for [[scheduling]] 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''{{efn|The term ''Quality of Service (QoS)'' initially arose in the context of communication networks but subsequently has commonly been applied at the application level.}}—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<ref name="Jensen 77" /><ref name="Gouda+ 77" /><ref name="Maynard+ 88 & 08" />).

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.,<ref name="Ravindran+ 05" /><ref name="Aldami+ 99" /><ref name="Burns+ 00" /><ref name="Prasad+ 03" /><ref name="Chen+ 96" />—and applied in civilian contexts.

{{anchor|examples}}
Some examples of the latter include: cyber-physical systems,<ref name="Tidwell+ 10" /> AI,<ref name="Ronén+ 99" /> multi-robot systems,<ref name="Barcís 20" /> drone scheduling,<ref name="Shireen Seakhoa-King+ 19" /> autonomous robots,<ref name="Baums 12" /> intelligent vehicle-to-cloud data transfers,<ref name="Ibarz+ 20" /> industrial process control,<ref name="Habets 19" /> transaction systems,<ref name="Haritsa+ 93"/> high performance computing,<ref name="Briceño+ 11" /> cloud systems,<ref name="Tunc+ 16" /> heterogeneous clusters,<ref name="Ravi+ 12" /> service-oriented computing,<ref name="Young+ 06" /> networking,<ref name="Wang+ 04" /> and memory management for real<ref name="Cho+ 09" /> and virtual<ref name="Feizabadi+ 07" /> machines. A steel mill example is briefly described in the Introduction of Clark's Ph.D. thesis.<ref name="Clark 90" />

TUFs and their utility interpretations (semantics), scales, and values are derived from domain-specific subject matter knowledge.<ref name="Clark+ 99" /><ref name="Maynard+ 88 & 08" /> A historically frequent interpretation of utility is actions' relative ''importance.''{{efn|''Scheduling'' based on importance is not the same as greedy ''dispatching'' based on importance.}} A framework for á priori assigning static utility values subject to strong constraints on system models has been devised,<ref name="Burns+ 00" /> 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]], including linear ones. See the depiction of some example TUFs.

TUF/UA papers in the research literature, with few exceptions, e.g.,<ref name="Locke 86" /><ref name="Ravindran+ 05" /><ref name="Li 04" /><ref name="Li+ 06" /><ref name="Burns+ 00" /><ref name="Chen+ 96" /> are for only either linear or piecewise linear<ref name="Guo+ 16"/> (including conventional deadline-based) TUFs because they are easier to specify and schedule. In many cases, the TUFs are only [https://en.wiktionary.org/wiki/monotonic_decreasing#:~:text=English-,Adjective,contrast%20this%20with%20strictly%20decreasing monotonically decreasing].

A [[constant function]] 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<ref name="Jensen 93" />—for example, consider a TUF having a sequence of downward steps, perhaps to approximate a smooth downward curve.{{efn|This is more general than Locke's introduction of the term ''critical time'' in Locke 86.}}

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{{efn|There is a discontinuity in either the function or its first or second derivative.}} 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]]<ref name="Erikson 14" /> 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.{{efn|For example, mathematical evidence theories such as [[Dempster-Shafer Theory]], [[imprecise probability]] theories, etc. may be used for certain system models having epistemic uncertainties.}} 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]].

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 {{see below|[[#Utility Accrual Scheduling|below]]}}.

A TUF (its shape and values) may be dynamically adapted by an application or its operational environment,<ref name="Jensen 93" /> independently for any actions currently either waiting or operating.{{efn|''Operating'' is used as the general case to include non-computational (e.g., mechatronic) actions as well as computational tasks that execute.}}

These adaptations ordinarily occur at discrete events—e.g., at an application mode change such as for ballistic missile flight phases.<ref name="Maynard+ 88 & 08" />

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''.<ref name="Gawiejnowicz 20a" /><ref name="Glazebrook 92" /> Time-dependent scheduling was introduced for (but is not limited to) certain real-time military applications, such as radar tracking systems.<ref name="Balli+ 07" /><ref name="Ho+ 93" />{{efn|Time-dependent scheduling (i.e., some actions' operation durations are functions of their starting times) is distinct from, and not limited to, real-time scheduling in the sense of actions having deadlines (or critical times).}}

==Utility Accrual Scheduling==

Multiple actions in a system may contend for access to sequentially exclusively{{efn|''Sequentially exclusive'' is a special case of shared access, used here for simplicity without loss of generality.}} 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.{{efn|Some UA schedulers may remove an overload in a greedy manner—cf. §7.5.1 in Locke 86.}}

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.<ref name="Clark+ 99" />

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''.<ref name="Gawiejnowicz 20a" /><ref name="Glazebrook 92" /><ref name="Balli+ 07" /><ref name="Ho+ 93" />

==Notes==
{{notelist|group=lower-alpha}}

==References==
{{reflist|refs=

<ref name="Jensen 77">E. Douglas Jensen. Chapter 3 ''Radar Scheduling,'' Section 1 ''The Scheduling Problem'' in Gouda+ 77 (unclassified version).</ref>

<ref name="Gouda+ 77">Mohamed G. Gouda, Yi-Wu Han, E. Douglas Jensen, Wesley D. Johnson, Richard Y. Kain (Editor). ''Distributed Data Processing Technology, Vol. IV, Applications of DDP Technology to BMD: Architectures and Algorithms,'' unclassified version, Defense Technical Information Center a047477, Honeywell Systems and Research Center, Minneapolis, MN, 1977.</ref>

<ref name="Jensen+ 85">E. Douglas Jensen, C. Douglas Locke, and Hideyuki Tokuda. ''A Time-Value Driven Scheduling Model for Real-Time Operating Systems,'' Proc. Symposium on Real-Time Systems, IEEE, 1985.</ref>

<ref name="Jensen 93">E. Douglas Jensen. ''A Timeliness Model for Asynchronous Decentralized Computer Systems,'' Proc. International Symposium on Autonomous Decentralized Systems, IEEE, 1993</ref>

<ref name="Tidwell+ 10">Terry Tidwell, Robert Glaubius, Christopher D. Gill and William D. Smart. ''Optimizing Expected Time Utility in Cyber-Physical Systems Schedulers,'' Proc. IEEE Real-Time Systems Symposium, 2010.</ref>

<ref name="Ronén+ 99">Yagil Ronén, Daniel Mossé, and Martha E. Pollack. ''Value-Density Algorithms for the Deliberation-Scheduling Problem,'' ACM SIGART Bulletin, Volume 7 Issue 2, 1996.</ref>

<ref name="Barcís 20">Michał Barcís, Agata Barcís, and Hermann Hellwagner. ''An Evaluation Model for Information Distribution in Multi-Robot Systems,'' Sensors, January 2020.</ref>

<ref name="Shireen Seakhoa-King+ 19">Shireen Seakhoa-King, Paul Balaji, Nicolas Trama Alvarez, and William J. Knottenbelt. ''Revenue-Driven Scheduling in Drone Delivery Networks with Time-Sensitive Service Level Agreements,'' Proc. 12th EAI International Conference on Performance Evaluation Methodologies and Tools, ACM, 2019.</ref>

<ref name="Ibarz+ 20">Jean Ibarz, Michaël Lauer, Matthieu Roy, Jean-Charles Fabre, Olivier Flébus. ''Optimizing Vehicle-to-Cloud Data Transfers using Soft Real-Time Scheduling Concepts'', Proc. 28th International Conference on Real-Time Networks and Systems, ACM, 2020.</ref>

<ref name="Baums 12">Aldis Baums. ''Automatic Control and Computer Sciences,'' Vol. 46, No. 6, Allerton Press, 2012.</ref>

<ref name="Habets 19">Rutger Habets. ''Improving the line performance of packaging line 41 at Heineken Zoeterwoude,'' Bachelor of Science project thesis, Industrial Engineering and Management, University of Twente, 2019.</ref>

<ref name="Haritsa+ 93">Jayant R. Haritsa, Jayant R., Michael J. Carey, and Miron Livney. ''Value-Based Scheduling in Real-Time Databases,'' VLDB Journal, 2 (2) 1993.</ref>

<ref name="Briceño+ 11">Luis Diego Briceño, Bhavesh Khemka, Howard Jay Siegel, Anthony A. Maciejewski, Christopher Groër, Gregory Koenig, Gene Okonski, and Steve Poole. ''Time Utility Functions for Modeling and Evaluating Resource Allocations in a Heterogeneous Computing System,'' Proc. IEEE International Symposium on Parallel and Distributed Processing, 2011.</ref>

<ref name="Tunc+ 16">Cihan Tunc, Nirmal Kumbhare, Ali Akoglu, Salim Hariri, Dylan Machovec, Howard Jay Siegel. ''Value of Service Based Task Scheduling for Cloud Computing Systems,'' Proc. International Conference on Cloud and Autonomic Computing, 2016.</ref>

<ref name="Ravi+ 12">Vignesh T. Ravi1, Michela Becchi2, Gagan Agrawal1, and Srimat Chakradhar. ''ValuePack: Value-Based Scheduling Framework for CPU-GPU Clusters,'' Proc. IEEE International Conference on High Performance Computing, Networking, Storage and Analysis, 2012.</ref>

<ref name="Young+ 06">Alvin AuYoung, Laura Grit, Janet Wiener, John Wilkes. ''Service contracts and aggregate utility functions,'' Proc. 15th IEEE International Symposium on High Performance Distributed Computing, 2006.</ref>

<ref name="Wang+ 04">Jinggang Wang and Binoy Ravindran. ''Time-Utility Function-Driven Switched Ethernet: Packet Scheduling Algorithm, Implementation, and Feasibility Analysis,'' IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 2, February 2004.</ref>

<ref name="Cho+ 09">Hyeonjoong Cho, Binoy Ravindran, Chewoo Na. ''Garbage Collector Scheduling in Dynamic, Multiprocessor Real-Time Systems,'' IEEE Transactions on Parallel and Distributed Systems 20(6), June 2009.</ref>

<ref name="Feizabadi+ 07">Shahrooz Feizabadi and Godmar Back. ''Garbage collection-aware utility accrual scheduling,'' Real-Time Systems Journal, July 2007, Volume 36, Issue 1–2, 2007.</ref>

<ref name="Clark+ 99">Raymond K. Clark, E. Douglas Jensen, Arkady Kanevsky, John Maurer, Paul Wallace, Tom Wheeler, Yun Zhang, Douglas M. Wells, Tom Lawrence, and Pat Hurley. ''An Adaptive, Distributed Airborne Tracking System,'' IEEE Parallel and Distributed Real-Time Systems, volume 1586 of LNCS, Springer-Verlag, 1999.</ref>

<ref name="Maynard+ 88 & 08">David P. Maynard, Samuel E. Shipman, Raymond K. Clark, J. Duane Northcutt, E. Douglas Jensen, Russell B. Kegley, Betsy A. Zimmerman, Peter J. Keleher. ''An Example Real-Time Battle Management Command and Control Application for Alpha,'' Section 8.2.1, Archons Project Technical Report, 1988, and public version 2008.</ref>

<ref name="Locke 86">C. Douglas Locke. ''Best-Effort Decision Making for Real-Time Scheduling,'' Ph.D. Thesis CMU-CS-86-134, Computer Science Department, Carnegie-Mellon University, 1986.</ref>

<ref name="Ravindran+ 05">Binoy Ravindran, E. Douglas Jensen, and Peng Li. ''On Recent Advances in Time/Utility Function Real-Time Scheduling and Resource Management,'' Proc. Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, 2005.</ref>

<ref name="Li 04">Peng Li. ''Utility Accrual Real-Time Scheduling: Models and Algorithms,'' Ph.D. dissertation, Virginia Polytechnic Institute and State University, 2004.</ref>

<ref name="Aldami+ 99">Saud A. Aldami and Alan Burns. ''Dynamic Value-Density for Scheduling Real-Time Systems,'' Proc. 11th Euromicro Conference on Real-Time Systems, IEEE, 1999.</ref>

<ref name="Chen+ 96">Ken Chen and Paul Muhlethaler. ''A Family of Scheduling Algorithms for Real-Time Systems Using Time Value Functions.'' Real-Time Systems, vol. 10 no. 3, Kluwer, 1996.</ref>

<ref name="Balli+ 07">Umut Balli, Haisang Wu, Binoy Ravindran, Jonathan Stephen Anderson, E. Douglas Jensen. ''Utility Accrual Real-Time Scheduling under Variable Cost Functions,'' IEEE Transactions on Computers, Volume 56, Number 3, March 2007.</ref>

<ref name="Clark 90">Raymond K. Clark. ''Scheduling Dependent Real-Time Activities,'' Ph.D. Dissertation, CMU-CS-90-155, Computer Science Department, Carnegie Mellon Univ., 1990.</ref>

<ref name="Li+ 06">Peng Li, Haisang Wu, Binoy Ravindran, and E. Douglas Jensen. ''A Utility Accrual Scheduling Algorithm for Real-Time Activities with Mutual Exclusion Resource Constraints,'' IEEE Transactions on Computers, vol. 55, no. 4, April 2006.</ref>

<ref name="Burns+ 00">Alan Burns, D. Prasad, A. Bondavalli, F. Di Giandomenico, K. Ramamritham, J. Stankovic, L. Strigini. ''The meaning and role of value in scheduling flexible real-time systems,'' Journal of Systems Architecture, Elsivier, 2000.</ref>

<ref name="Prasad+ 03">Divya Prasad, Alan Burns, and Martin Atkins. ''The Valid Use of Utility in Adaptive Real-Time Systems.'' Real-Time Systems, Kluwer, 2003.</ref>

<ref name="Guo+ 16">Zhishan Guo and Sanjoy Buruah. ''A Neurodynamic Approach for Real-Time Scheduling via Maximizing Piecewise Linear Utility'', IEEE Transactions on Neural Networks and Learning Systems, vol. 27 no. 2, February 2016.</ref>

<ref name="Erikson 14">Jeremy P. Erickson. ''Managing Tardiness Bounds and Overload in Soft Real-Time Systems'', Ph.D. dissertation, University of North Carolina, 2014.</ref>

<ref name="Gawiejnowicz 20a">Stanislaw Gawiejnowicz. ''A review of four decades of time-dependent scheduling: main results, new topics, and open problems,'' Journal of Scheduling 23, 3–47, Springer, 2020.</ref>

<ref name="Glazebrook 92">K. D. Glazebrook. ''Single-machine scheduling of stochastic jobs subject to deterioration or delay,'' Naval Research Logistics 39, no. 5, Wiley, 1992.</ref>

<ref name="Ho+ 93">Kevin I-J. Ho, Joseph Y-T. Leung and W-D. Wei. ''Complexity of scheduling tasks with time-dependent execution times,'' Information Processing Letters 48 (1993), no. 6, Elsevier, 20 December 1993.</ref>



}}

==External links==
* [https://www.real-time.org Real-Time for the Real World.]
* [https://www.ssrg.ece.vt.edu/allpapers.php 2006-2009, Systems Software Research Group, Binoy Ravindran, ECE, Virginia Tech.]
* [https://www.stern.nyu.edu/om/faculty/pinedo/schedtheory/book5/index.html Michael L. Pindo, ''Scheduling: Theory, Algorithms, and Systems,'' 5th ed., 2015.]
* [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 {{ISBN|978-3-662-59362-2}}, Springer, 2020.
* [https://www.academia.edu/15210217/Fifty_years_of_scheduling_a_survey_of_milestones?auto=download&email_work_card=download-paper Chris N. Potts and Vitaly A. Strusevich, ''Fifty Years of Scheduling: A Survey of Milestones'' (2009)]
* [https://www.springer.com/journal/10951 Journal of scheduling.]
* [http://www.schedulingconference.org/ Multidisciplinary International Conference on Scheduling.]
* [https://www.researchgate.net/project/The-Third-International-Workshop-on-Dynamic-Scheduling-Problems-IWDSP-2020 International Workshop on Dynamic Scheduling Problems.]

{{DEFAULTSORT:Time-Utility Function}}
[[Category:Real-time computing]]
[[Category:Optimal scheduling]]
[[Category:Quality of service]]
[[Category:Software performance management]]

Time-utility function - Revision history

imported>BD2412: Clean up spacing around commas and other punctuation fixes, replaced: ,A → , A, ,c → , c