Sub-problem optimization of supply chain planning problems
View Patent ↗A system and method is disclosed for optimizing supply chain planning problems associated with a supply chain network. The system includes a supply chain planner coupled with one or more supply chain entities. The supply chain planner determines a supply chain plan for managing the flow of one or more items through the supply chain network.
1. A system comprising:
a computer, comprising at least two processors and a memory, configured to:
model a supply chain planning problem as a hierarchy of linear programming problems based, at least in part, on data describing a flow of one or more items through one or more supply chain entities, wherein each level of the hierarchy is associated with an objective function;
split the supply chain planning problem into a master-problem and a sub-problem, wherein the master-problem and the sub-problem comprise constraints associated the one or more supply chain entities;
decompose the sub-problem into independent sub-problems;
solve each level of the hierarchy for the master problem;
solve at least two of the independent sub-problems in parallel using the at least two processors; and
generate a supply chain plan by converging each level of the hierarchy for the master-problem and independent sub-problems into the supply chain plan.
2. The system of claim 1 , wherein the computer is configured to solve each level of the hierarchy for the master problem by:
using a column generation technique to solve each level of the hierarchy for the master-problem by interacting with each of the independent sub-problems and generating columns using a solution of the master-problem.
3. The system of claim 2 , wherein the computer is configured to solve at least two of the independent sub-problems in parallel using the at least two processors by:
modeling a solution of the independent sub-problems as one or more of:
a shortest path problem; and
a minimum cost flow.
4. The system of claim 3 , wherein the objective function is modeled as a business goal for the one or more supply chain entities.
5. The system of claim 4 , wherein the objective function of at least one level is selected from at least one of:
maximizing demand satisfaction;
minimizing inventory; and
minimizing a use of preferred alternatives.
6. The system of claim 5 , wherein the constraints comprise one or more of:
lead time constraints that describe a time required for at least one of the one or more supply chain entities to supply the one or more items to another of the one or more other supply chain entities;
lot size constraints that define a quantity of the one or more items that may be transferred;
capacity constraints that describe a maximum quantity of the one or more items that may be produced at the one or more supply chain entities; and
capacity constraints that describe a maximum quantity of the one or more items that may be stored at the one or more supply chain entities.
7. The system of claim 6 , wherein a solution for a subsequent level of the hierarchy is not degraded by a solution to a prior level of the hierarchy.
8. A computer-implemented method, comprising:
modeling a supply chain planning problem as a hierarchy of linear programming problems based, at least in part, on data describing a flow of one or more items through one or more supply chain entities, wherein each level of the hierarchy is associated with an objective function;
splitting the supply chain planning problem into a master-problem and a sub-problem, wherein the master-problem and the sub-problem comprise constraints associated with the one or more supply chain entities;
decomposing the sub-problem into independent sub-problems;
solving each level of the hierarchy for the master problem;
solving at least two of the independent sub-problems in parallel using at least two processors; and
generating a supply chain plan by converging each level of the hierarchy for the master-problem and independent sub-problems into the supply chain plan.
9. The computer-implemented method of claim 8 , wherein solving each level of the hierarchy for the master problem comprises:
using a column generation technique to solve each level of the hierarchy for the master-problem by interacting with each of the independent sub-problems and generating columns using a solution of the master-problem.
10. The computer-implemented method of claim 9 , wherein solving at least two of the independent sub-problems in parallel using at least two processors comprises:
modeling a solution of the independent sub-problems as one or more of:
a shortest path problem; and
a minimum cost flow.
11. The computer-implemented method of claim 10 , wherein the objective function is modeled as a business goal for the one or more supply chain entities.
12. The computer-implemented method of claim 11 , wherein the objective function of at least one level is selected from at least one of:
maximizing demand satisfaction;
minimizing inventory; and
minimizing a use of preferred alternatives.
13. The computer-implemented method of claim 12 , wherein the constraints comprise one or more of:
lead time constraints that describe a time required for at least one of the one or more supply chain entities to supply the one or more items to another of the one or more other supply chain entities;
lot size constraints that define a quantity of the one or more items that may be transferred;
capacity constraints that describe a maximum quantity of the one or more items that may be produced at the one or more supply chain entities; and
capacity constraints that describe a maximum quantity of the one or more items that may be stored at the one or more supply chain entities.
14. The computer-implemented method of claim 13 , wherein a solution for a subsequent level of the hierarchy is not degraded by a solution to a prior level of the hierarchy.
15. A non-transitory computer-readable medium embodied with software, the software when executed using one or more computer systems is programmed to:
model a supply chain planning problem as a hierarchy of linear programming problems based, at least in part, on data describing a flow of one or more items through one or more supply chain entities, wherein each level of the hierarchy is associated with an objective function;
split the supply chain planning problem into a master-problem and a sub-problem, wherein the master-problem and the sub-problem comprise constraints associated with the one or more supply chain entities;
decompose the sub-problem into independent sub-problems;
solve each level of the hierarchy for the master problem;
solve at least two of the independent sub-problems in parallel using at least two processors; and
generate a supply chain plan by converging each level of the hierarchy for the master-problem and independent sub-problems into the supply chain plan.
16. The non-transitory computer-readable medium of claim 15 , wherein the software when executed using one or more computer systems is programmed to solve each level of the hierarchy for the master problem by:
using a column generation technique to solve each level of the hierarchy for the master-problem by interacting with each of the independent sub-problems and generating columns using a solution of the master-problem.
17. The non-transitory computer-readable medium of claim 16 , wherein the software when executed using one or more computer systems is programmed to solve at least two of the independent sub-problems in parallel using the at least two processors by:
modeling a solution of the independent sub-problems as one or more of:
a shortest path problem; and
a minimum cost flow.
18. The non-transitory computer-readable medium of claim 17 , wherein the objective function is modeled as a business goal for the one or more supply chain entities.
19. The non-transitory computer-readable medium of claim 18 , wherein the objective function of at least one level is selected from at least one of:
maximizing demand satisfaction;
minimizing inventory; and
minimizing a use of preferred alternatives.
20. The non-transitory computer-readable medium of claim 19 , wherein the constraints comprise one or more of:
lead time constraints that describe a time required for at least one of the one or more supply chain entities to supply the one or more items to another of the one or more other supply chain entities;
lot size constraints that define a quantity of the one or more items that may be transferred;
capacity constraints that describe a maximum quantity of the one or more items that may be produced at the one or more supply chain entities; and
capacity constraints that describe a maximum quantity of the one or more items that may be stored at the one or more supply chain entities.