System and method for solving large scale supply chain planning problems with integer constraints

Patent metadata

Field	Value
Publication number	US-9754232-B2
Application number	US-201313867310-A
Country	US
Kind code	B2
Filing date	Apr 22, 2013
Priority date	Aug 26, 2009
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

Abstract

A system and method is disclosed for solving supply chain planning problems. The system includes a database that stores data representing a planning problem of a supply chain network and a computer that accesses the planning problem of the supply chain network stored in the database and models the planning problem as a network of nodes and edges. The computer further generates a hierarchical linear programming solution of the planning problem and applies advanced heuristics to the generated hierarchical linear programming solution. The computer still further formulates a mixed integer program to generate an optimized global hierarchical solution and stores the generated optimized global hierarchical solution in the database.

First claim

What is claimed is:

1. A system, comprising:
a supply chain network comprising one or more supply chain entities that produce one or more products, comprising:
one or more buffers comprising one or more material storage and transition units;
one or more material operations;
a demand from the one or more supply chain entities for the one or more products; and
a planner, comprising a computer having a processor and a non-transitory computer readable medium, configured to generate a supply chain model wherein the one or more buffers are represented by nodes and the one or more material operations are represented by edges that connect the nodes, the planner further configured to:
divide a planning horizon of the generated supply chain model into one or more time buckets;
prioritize and model one or more business objectives as a hierarchy of objective functions;
automatically solve the hierarchy of objective functions by variable fixing;
automatically obtain an integer feasible solution of the hierarchy of objective functions; and
automatically obtain a global hierarchical solution; and

causing one or more of the supply chain entities to perform the one or more material operations to produce the one or more products, based at least in part, on the global hierarchical solution that satisfies the demand of the one or more supply chain entities.

2. The system of claim 1 , wherein the planner obtains the integer feasible solution of the hierarchy of objective functions by:
sorting the one or more buffers from downstream to upstream;
calculating the time bucket-wise consumption and production profiles for the one or more time buckets from downstream time bucket to upstream;
processing a lot size and a resource setup;
checking for material availability from upstream to downstream for the one or more buffers;
determining a material and resource feasible integer solution; and
determining the global hierarchical solution.

3. The system of claim 2 , wherein determining the global hierarchical solution comprises:
generating a model by:
fixing integer variables according to the material and resource feasible integer solution and solving for the topmost objective function;
converting hierarchical objective functions to constraints by adding slack and surplus variables;
introducing integer variables and integer constraints and calculating values for all the objective functions;
assigning one or more deviation-based normalization coefficients;
assigning one or more hierarchy-based objective coefficients;
grouping objective violation variables; and
assigning one or more intra-group objective coefficients; and

solving the model as a mixed integer problem.

4. The system of claim 3 , wherein assigning hierarchy-based objective coefficients comprises:
calculating one or more objective coefficients as decreasing exponents of a fixed base; and
each of the one or more objective coefficients are a multiplication of a hierarchy coefficient and a normalization coefficient.

5. The system of claim 4 , further comprising:
sources of materials comprising one or more of raw materials, inventory, work-in-progress, purchase orders and future procurements from one or more supply chain entities, the source of materials are represented as one or more nodes not having any upstream nodes;
customer orders for the one or more products are represented as one or more nodes not having any downstream nodes;
planned manufacturing operations are represented by one or more nodes having one or more upstream nodes and one or more downstream nodes; and
one or more inputs and one or more outputs are represented by edges.

6. The system of claim 5 , wherein:
an edge between two buffer nodes represents processing of material and an edge between different time buckets for the same buffer represents inventory carried forward.

7. The system of claim 6 , wherein the demand is one or more operational objectives of the one or more supply chain entities and comprises one or more of demand, safety stock limits, minimizing inventory, reducing backlog, obtaining a particular product mix, maintaining proportionality, reducing use of alternate items, and optimizing profit.

8. A computer-implemented method comprising:
generating a supply chain model of a supply chain network comprising one or more buffers comprising one or more material storage and transition units, one or more material operations, a demand from one or more supply chain entities for the one or more products, wherein the one or more buffers are represented by nodes and the one or more material operations are represented by edges that connect the nodes;
dividing a planning horizon of the generated supply chain model into one or more time buckets;
prioritizing and modeling one or more business objectives as a hierarchy of objective functions;
automatically solving the hierarchy of objective functions by variable fixing;
automatically obtaining an integer feasible solution of the hierarchy of objective functions;
automatically obtaining a global hierarchical solution; and
causing one or more supply chain entities to perform the one or more material operations to produce, the one or more products, based at least in part, on the global hierarchical solution that satisfies the demand of the one or more supply chain entities.

9. The computer-implemented method of claim 8 , wherein obtaining the integer feasible solution of the hierarchy of objective functions comprises:
sorting the one or more buffers from downstream to upstream;
calculating the time bucket-wise consumption and production profiles for the one or more time buckets from downstream time bucket to upstream;
processing a lot size and a resource setup;
checking for material availability from upstream to downstream for the one or more buffers;
determining a material and resource feasible integer solution; and
determining the global hierarchical solution.

10. The computer-implemented method of claim 9 , wherein determining the global hierarchical solution comprises:
generating a model by:
fixing integer variables according to the material and resource feasible integer solution and solving for the topmost objective function;
converting hierarchical objective functions to constraints by adding slack and surplus variables;
introducing integer variables and integer constraints and calculating values for all the objective functions;
assigning one or more deviation-based normalization coefficients;
assigning one or more hierarchy-based objective coefficients;
grouping objective violation variables; and
assigning one or more intra-group objective coefficients; and

solving the model as a mixed integer problem.

11. The computer-implemented method of claim 10 , wherein assigning hierarchy-based objective coefficients comprises:
calculating one or more objective coefficients as decreasing exponents of a fixed base; and
each of the one or more objective coefficients are a multiplication of a hierarchy coefficient and a normalization coefficient.

12. The computer-implemented method of claim 11 , further comprising:
representing, by the planner, as one or more nodes not having any upstream nodes, sources of materials comprising one or more of raw materials, inventory, work-in-progress, purchase orders and future procurements from one or more supply chain entities;
representing, by the planner, as one or more nodes not having any downstream nodes, customer orders for the one or more products;
representing, by the planner, as one or more nodes having one or more upstream nodes and one or more downstream nodes, planned manufacturing operations; and

Assignees

• Jda Software Group Inc

Inventors

• Kamath Narasimha B
• Shekhar Tushar

Classifications

• G06Q10/06

  Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling · CPC title

• G06Q10/0633 Primary

  Workflow analysis · CPC title