Control of items in a complex system by using fluid models and solving continuous linear programs

• US 20060015309A1
• Filed: 05/02/2005
• Published: 01/19/2006
• Est. Priority Date: 07/26/2002
• Status: Active Grant

• Current Assignee: Gideon Weiss
• Original Assignee: Gideon Weiss
• Inventors: Weiss, Gideon
• Granted Patent: US 7,433,742 B2
• Time in Patent Office: Days
• US Class Current: 703/6
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

A method and apparatus for the control of a system comprising of a plurality of items through the scheduling of actions and the allocation of resources is disclosed. Primary areas of utility include manufacturing systems, city wide vehicle traffic control, multiple project scheduling, communications networks and economic systems. The method and apparatus comprise modeling the parts in such a system as fluid, formulating the control problem as a continuous linear program, using a novel algorithm to solve it, displaying the fluid solution in a meaningful way, and using the fluid solution in the control of the system.

Claims

1. An apparatus for optimizing the performance of a controlled system over a plurality of times, said apparatus comprising:

a plurality of process control devices for controlling said controlled system in response to control signals from the apparatus,

a plurality of sensors for sensing variable conditions of the controlled system by the apparatus,

a means for modeling said controlled system by a conceptual fluid-model,

a means for calculating optimal control signals for the control of said controlled system,

wherein said controlled system comprises a plurality of discrete items, a plurality of actions, and a plurality of resources, where at each of said times each of said items is in one of a plurality of classes, and where application of one of said actions to one of said items in one of said classes at one of said times will change the class of the item, and where said application of one of said actions to one of said items at one of said times will consume some of said resources, and wherein the control of the said controlled system comprises the timing of said actions and the allocation of said resources to said actions, and wherein said means of the apparatus for modeling said controlled system by a conceptual fluid-model comprise;

a plurality of state functions that denote levels of fluids in buffers as a function of time, where the fluid in a buffer at time t approximates the number of items in a corresponding class in the controlled system around the time t, and

a plurality of control functions that denote flow rates as a function of time, where a flow rate at time t represents the number of applications of a corresponding action in the real system around the time t, and

a linear relationship between the flow rates and the rates of change of the state of the fluid-model system at time t, and

a linear relationship between the flow rates of the fluid-model system at time t and the rate of consumption of resources,

and wherein said means of the apparatus for calculating optimal control signals comprise an algorithm for the solution of separated continuous linear programming problems, and wherein the operation of the apparatus comprises the repeated applications of the steps;

(a) setting current-time to 0, and setting time-horizon to a predetermined value T, and using the apparatus sensing devices to sensing current-state of the controlled system, and

sensing the predicted exogenous inputs into the controlled system over the time horizon, and

sensing the predicted levels of available resources over the time horizon, and

sensing the predicted rates of reward, per item in each class, and per action, over the time horizon,

 

and formulating a separated continuous linear programming optimization problem for the fluid-model system from the sensed data of the controlled system,

(b) solving said separated continuous linear programming optimization problem, by an algorithm comprising a sequence of iterations, each of said iterations comprising

a current solution valid in a current validity range, and

an updated solution valid in an updated validity range, and

a calculation of the updated solution from the current solution, said calculation comprising the steps of;

solving a linear programming problem relating to rates, and determining if a need for solving a sub-problem exists, and if the need exists then;

formulating the sub-problem, and

solving the sub-problem by a recursive call to a version of the algorithm,

 

to obtain a fluid solution, comprising the optimal values of the controls of the fluid system and the optimal values of the states of the fluid system for all the times from 0 to T,

(d) producing control signals for controlling the real system in accordance with the optimal solution of the fluid-model system.

where the repeated application of the steps (a), (b), and (c) is performed at a plurality of predetermined decision times.

2. A method for optimizing a real system, said system comprising a plurality of state functions which describe the state of the system as a functions of time, and a plurality of control functions which enable the control of the system over time, said method providing a means for determining values of the control functions over time and of the state functions over time, wherein the control functions and the state functions are subject to linear relations over time and satisfy linear resource constraints over time, and rewards of the system are linear functions of the controls and of the states over time, so that the problem of determining the said values of the control and state functions can be formulated as a separated continuous linear programming problem, the method comprising:

formulating said separated continuous linear programming problem,

solving said separated continuous linear programming problem and determining said control functions over time and said state functions over time,

implementing said control functions over time and said state functions over time to operate the system,

wherein solving the formulated separated continuous linear programming problem is achieved by an algorithm comprising;

solving a parametric range of problems,

starting from an optimal solution of an initial separated continuous linear programming problem at the beginning of the whole parameter range,

terminating with an optimal solution of the formulated separated continuous linear programming problem at the end of the whole parameter range,

performing one or more iterations where each successive iteration provides solutions for a successive range of values of the parameter,

wherein the algorithm is characterized by representing the solution for a range of values of the parameter by means of a concise description, comprising;

a finite sequence of adjacent bases, denoted by B₁, . . . , B_N, where these bases determine the values of the controls in successive adjacent intervals of time from 0 to the time horizon T,

a set of equations to determine the breakpoint times 0=t₀<

t₁<

. . . <

t_N=T between said successive adjacent intervals of time,

wherein the equations change smoothly with the change in the value of the parameter,

and each of the iterations of the algorithm comprising

starting from a solution for a value of the parameter given by a particular sequence of bases B₁, . . . , B_N, then

determining the boundaries of a first range of parameter values for which the same sequence of bases B₁, . . . , B_N determines the solutions, then

using the solution for the value of the parameter at one of the boundaries of said first range of parameter values to determine;

0 or 1 or more than 1 bases that need to be deleted from the sequence of bases B₁, . . . , B_N, and

0 or 1 or more than 1 bases that need to be inserted in the sequence of bases B₁, . . . , B_N,

and then eliminating and inserting said bases, to obtain a new sequence of bases, which describes the solutions for a second range of values of the parameter which is adjacent to the first range.