×

Methods and apparatus for efficient resource allocation

  • US 4,885,686 A
  • Filed: 01/12/1987
  • Issued: 12/05/1989
  • Est. Priority Date: 01/12/1987
  • Status: Expired due to Term
First Claim
Patent Images

1. A method for allocating available industrial facilities among users of said facilities, subject to constraints on said allocations, to minimize the total cost of providing said facilities, said method starting with a initial tentative facilities assignment and comprising the steps of:

  • tentatively assigning said available facilities to said users in accordance with a specified deterministic process to form a tentative facilities assignment characterized by a total cost that is lower than the cost of preceding tentative facilities assignments;

    repeating said step of tentatively assigning when said total cost fails to meet a preselected criterion; and

    allocating said facilities in accordance with the last of said tentative facilities assignments when said total cost meets said preselected criterion;

    whereinsaid allocations to said users and said available industrial facilities form linear constraint relationships; and

    said preselected deterministic process is a modified Karmarkar algorithm whereineach said assignment is determined by normalizing the previous assignment with respect to constraints on said allocations,during each said assignment, forming a tentative facilities assignment by (a) separating said constraint relationships into a sum of a first subset of constraint relationships and a second subset of constraint relationships, where said first subset of constraint relationships corresponds to those users that affect a number of said constraints in excess of a preselected proportion of said constraints, and said second subset of constraint relationships corresponds to the remaining users, and (b) separately operating on said subsets of constraint relationships in the course of said assignment.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×