Resource constrained task scheduling

摘要

The use of linear programming may enable the achievement of real-time task execution prioritization. A linear model may be constructed based at least on a set of computing tasks, a linearly expressible goal for the set of computing tasks, one or more linear resource constraints, and one or more computing task dependencies. The linear model is then used to calculate a shadow price for each of a plurality of resource time prediction constraints, in which each shadow price may represent a priority value for a corresponding computing task. When a computing resource becomes available, a computing task with a highest priority value that is able to use the computing resource may be executed.

主权项

1. A computer-implemented method, comprising:
constructing a linear model using a matrix variable having a value that represents a speed at which a computing task of a set of computing tasks is executing on a computing resource at a particular time, the linear model including the set of computing tasks, a linearly expressible goal of completing the set of computing tasks in a shortest duration of time, one or more linear resource constraints, and one or more computing task dependencies; solving the one or more linear resource constraints included in the linear model using at least one of Dantzig's simplex algorithm, Karmarkar's algorithm, or a branch-and-cut method with Dantzig's simplex algorithm to obtain resource time prediction constraints; calculating, using one or more hardware processors, shadow prices for the resource time prediction constraints using a dual problem solving technique, wherein individual shadow prices represent a priority value for a corresponding computing task; storing individual computing tasks of the set of computing tasks in a queue ordered according to corresponding shadow prices; selecting, from the queue, a particular computing task with a highest priority value indicated by the corresponding shadow price that is able to use an available computing resource; and executing, by the available computing resource, the particular computing task with the highest priority value selected from the queue.