A METHOD FOR SUPPLY CHAIN DECOMPOSITION
First Claim
1. A method for decomposing a linear program comprising:
- relaxing material balance and sourcing constraints of said linear program based on stocking point criteria;
initially solving the linear program with relaxed material balance and sourcing constraints to produce an initial solution;
replacing variables in said linear program with constants based on said initial solution;
restoring said material balance and sourcing constraints; and
finally solving the linear program using said constants and with all constraints in place to obtain a complete solution of said linear program.
1 Assignment
0 Petitions
Accused Products
Abstract
The invention provides a method and system for solving a linear program having constraints in a production planning system. The invention first determines which of the constraints can be temporarily relaxed based on stocking point criteria. The stocking point criteria relates to time dependent stocking points that include part numbers, locations of parts identified by the part numbers, and the time periods when the parts will be available. The invention relaxes the constraints that can be relaxed and decomposes the linear program into smaller independent linear programs. The invention initially solves the smaller independent linear programs with relaxed constraints (simultaneously in parallel) to produce an initial solution. Next, the invention replaces variables in the linear program with constants based on this initial solution. After this the invention restores the material balance and sourcing constraints and finally solves (re-solves) the linear program using the constants and with all constraints in place to obtain a complete solution of the linear program.
33 Citations
21 Claims
-
1. A method for decomposing a linear program comprising:
-
relaxing material balance and sourcing constraints of said linear program based on stocking point criteria;
initially solving the linear program with relaxed material balance and sourcing constraints to produce an initial solution;
replacing variables in said linear program with constants based on said initial solution;
restoring said material balance and sourcing constraints; and
finally solving the linear program using said constants and with all constraints in place to obtain a complete solution of said linear program. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for solving a linear program having constraints in a production planning system, said method comprising:
-
determining which of said constraints can be temporarily relaxed;
relaxing selected constraints of said linear program based on said determining process;
decomposing said linear program into smaller independent linear programs;
initially solving said smaller independent linear program with relaxed constraints to produce an initial solution;
replacing variables in said linear program with constants based on said initial solution;
restoring said material balance and sourcing constraints; and
finally solving said linear program using said constants and with all constraints in place to obtain a complete solution of said linear program. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A method for solving a linear program having constraints in a production planning system, said method comprising:
-
determining which of said constraints can be temporarily relaxed based on stocking point criteria that relates to time dependent stocking points comprising part numbers, locations of parts identified by said part numbers, and the time periods when said parts will be available;
relaxing selected constraints of said linear program based on said determining process;
decomposing said linear program into smaller independent linear programs;
initially solving said smaller independent linear program with relaxed constraints to produce an initial solution;
replacing variables in said linear program with constants based on said initial solution;
restoring said material balance and sourcing constraints; and
finally solving the linear program using said constants and with all constraints in place to obtain a complete solution of said linear program. - View Dependent Claims (16, 17, 18, 19, 20)
-
-
21. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for solving a linear program having constraints in a production planning system, said method comprising:
-
determining which of said constraints can be temporarily relaxed;
relaxing selected constraints of said linear program based on said determining process;
decomposing said linear program into smaller independent linear programs;
initially solving said smaller independent linear program with relaxed constraints to produce an initial solution;
replacing variables in said linear program with constants based on said initial solution;
restoring said material balance and sourcing constraints; and
finally solving said linear program using said constants and with all constraints in place to obtain a complete solution of said linear program.
-
Specification