UTILITY-OPTIMIZED SCHEDULING OF TIME-SENSITIVE TASKS IN A RESOURCE-CONSTRAINED ENVIRONMENT

摘要

Systems and methods implementing utility-maximized scheduling of time-sensitive tasks in a resource constrained-environment are described herein. Some embodiments include a method for utility-optimized scheduling of computer system tasks performed by a processor of a first computer system that includes determining a time window including a candidate schedule of a new task to be executed on a second computer system, identifying other tasks scheduled to be executed on the second computer system within said time window, and identifying candidate schedules that each specifies the execution times for at least one of the tasks (which include the new task and the other tasks). The method further includes calculating an overall utility for each candidate schedule based upon a task utility calculated for each of the tasks when scheduled according to each corresponding candidate schedule and queuing the new task for execution according to a preferred schedule with the highest overall utility.

主权项

1. A system for scheduling tasks in a computer system, the system comprising:
a portal module configured to receive a task to be scheduled for execution within a computer system from a device, the received task including a time dependent task utility function that includes a constant or increasing task utility value until reaching a time deadline; a schedule optimizer module configured to determine a time window for the received task to be scheduled for execution on the computer system based on the time dependent task utility function of the received task; the schedule optimizer module configured to identify a plurality of other tasks previously scheduled to be executed on the computer system within the time window of the received task; the schedule optimizer module configured to identify a plurality of candidate schedules, the plurality of candidate schedules including a first candidate schedule and a second candidate schedule, the first and second candidate schedules being different scheduling combinations of the received task and the plurality of other tasks; a utility estimator module configured to calculate a task utility value for each task included within the first and second candidate schedules based upon a corresponding time dependent task utility function; the utility estimator module configured to calculate a first overall utility value for the first candidate schedule based on the calculated task utility values for the tasks within the first candidate schedule and a second overall utility value for the second candidate schedule based on the calculated task utility values for the tasks within the second candidate schedule; the schedule optimizer module configured to select a schedule among the plurality of candidate schedules based on the first and second overall utility values; and a workload scheduling module configured to queue the received task for execution according to the selected schedule.