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

• US 20030158611A1
• Filed: 07/26/2002
• Published: 08/21/2003
• Est. Priority Date: 08/06/2001
• Status: Active Grant

• Current Assignee: Gideon Weiss
• Original Assignee: Gideon Weiss
• Inventors: Weiss, Gideon
• Granted Patent: US 6,922,593 B2
• Time in Patent Office: Days
• US Class Current: 700/31
• CPC Class Codes: G05B 17/02 electric

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. A method for control of a real system over a plurality of times, said real system comprising a plurality of 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, said control comprising timing of said actions and allocation of said resources to said actions, and said method optimizing the system by maximizing a plurality of rewards accrued by the system over time, said method comprising the steps of:

(a) modeling the real system by a conceptual fluid-model system, said conceptual fluid-model system comprising;

state of the fluid-model system given by 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 real system around the time t, and

controls of the fluid-model system given by 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, then

(b) formulating a separated continuous linear programming optimization problem for the fluid-model system from data of the real system, comprising;

current-time denoted as 0, and time-horizon T, and

current-state of the real-system which determines the state of the fluid-model system at time 0, and

predicted exogenous inputs into the real system over the time horizon, and

predicted levels of available resources over the time horizon, and

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

(c) solving said separated continuous linear programming optimization problem, 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, and finally

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

2. A method as in claim 1 wherein said system is a manufacturing system and said items comprise parts manufactured by the system and actions comprise processing of parts and classes comprise stages of completion of parts and resources comprise machines used to process the parts.

3. A method as in claim 1 wherein said system is a traffic system and said items comprise vehicles and said resources comprise road sections and intersections and actions comprise traveling along a road section and routing at an intersection, and classes comprise the location of vehicles and their destinations.

4. A method as in claim 1 wherein said system is a communication system, and said item are messages, classified by the route they travel, and actions are allocations of transmission rates of items along routes, and resources consumed by an action are bandwidths of the links along the route.

5. A method as in claim 1 wherein said system is a multi-project scheduling system and said items comprise activities required by projects, and actions comprise the performance of activities, and activities are classified according to type of activity which is common to all projects of the multi-project, and performance of activities of each class consumes shared resources.

6. A method as in claim 1 wherein said system is a supply chain management system, said system comprising orders of finished goods as exogenous input, and said items comprise items ordered at the various stages of the supply chain to fulfill said orders of finished goods, and actions provide the supply of the items along the stages of the supply chain, subject to lead times and to capacity constraints.

7. A method as in claim 1 wherein said system is an economic input output system, comprising a plurality of classes of assets, where the state of the system at any of the plurality of times is the level of the assets of the various classes, and a plurality of activities, which use some of the plurality of assets as input to produce an asset as output, the level of activity determining the rates of change in asset levels, according to a linear input output matrix of coefficients, and activities use up resources in proportion to levels of activities.

8. The method of claim 1, wherein the control step (d) of the method comprises the use of the fluid solution for design purposes, where the designer of the real system explores a new design by modeling the system according to the new design, formulating the fluid problem for the new design, solving and displaying the solution and observing the effect of the new design on the fluid solution, and using these observations in assessing the new design.

9. The method of claim 1, wherein the control step (d) of the method comprises the use of the fluid solution for planning purposes, where the planner of the real system explores a plan by formulating the fluid problem for the data of the new plan, comprising planned exogenous inputs, planned levels of available resources, and planned reward rates, solving and displaying the solution and observing the effect of the new plan on the fluid solution, and using these observations in assessing the plan.

10. The method of claim 1, wherein the control step (d) of the method comprises the use of the fluid solution for the purpose of forecasting and performance evaluation of the system, where the system manager will observe the fluid solution and will derive from it forecasts of timing of events and forecasts of quantities, and average performance measures such as cost rates, flow rates, and resource utilization.

11. The method of claim 1, wherein the control step (d) involves hierarchical control of the system, where the fluid solution is used by an upper level controller to set goals for a plurality of lower level controllers each of which is responsible for a part of the system, and each of the lower level controllers uses the goals assigned to it by the upper level controller to control her part of the system.

12. The method of claim 1, wherein the control step (d) involves tracking of the fluid solution by the actions taken in the real system.

13. The method of claim 1, comprising the additional step:

(e) repeating steps (b), (c), (d), at a plurality of new decision-times so that each repetition comprises

performing step (b) of claim 1 where the current-time 0 is the new decision-time, and the current time horizon T is the new decision-time plus T, and the current state of the system is updated to the state at the new decision-time, and the predicted exogenous inputs are updated, and the resource availabilities are updated, and the reward rates are updated to comprise the predictions at the new decision time, and

performing step (c) of claim 1 to obtain the fluid solution for the updated times from 0 to T, and

performing step (d) of claim 1, wherein controlling the real-system following the new decision-time is according to the fluid solution of the updated problem.

14. 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 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 state 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, 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.

15. 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.

16. A graphic display of a system, said system comprising a plurality of items, where each said items is in one of a plurality of classes, and evolution of the system over a plurality of times comprises some changes in the classes of the items, and said system can be approximated by a plurality of state functions, where each state function corresponds to one class, and the value of the state function at each of the plurality of times approximates the number of item in the system belonging to the corresponding class at that time, the graphic display comprising a plot of each of the state functions as a function of time, and the grouping of the plots of the plurality of the state functions in such a way that the approximate behavior of the entire system over time can be viewed from the graphic display.

17. The graphic display of claim 16, with the addition of a plurality of horizontal lines in the plot of each state function as a function of time, where said horizontal lines display the position of a plurality of sampled items in the buffer, and where said lines do not intersect each other, and where each line represents a single item from the time that it enters the buffer until the time that it leaves the buffer.

18. The graphic display of claim 16, with the addition of a graphic user interface which allows a user to interactively move some of the horizontal lines which represent items, and where the graphic user interface updates the other horizontal lines of the graphic display whenever the user moves one of the lines.