×

Method and system for scheduling using a facet ascending algorithm or a reduced complexity bundle method for solving an integer programming problem

  • US 5,715,165 A
  • Filed: 12/23/1994
  • Issued: 02/03/1998
  • Est. Priority Date: 12/23/1994
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for scheduling a sequence of events which are subject to a plurality of constraints, comprising the steps of:

  • defining the events and constraints in terms of an integer programming expression;

    applying Lagrangian relaxation to the integer programming expression to form a Lagrangian dual function;

    solving the Lagrangian dual function using a facet ascending algorithm, said facet ascending algorithm calculating an intersection of adjacent facet and moving along the facets on the intersection;

    scheduling the sequence of events in accordance with the resolved Lagrangian dual function; and

    performing the events in response to said schedule.

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