Continuous production planning using a transition matrix

• US 8,560,363 B1
• Filed: 06/19/2002
• Issued: 10/15/2013
• Est. Priority Date: 06/19/2002
• Status: Expired due to Fees

• Current Assignee: Blue Yonder Group, Inc. (Panasonic Holdings Corporation)
• Original Assignee: JDA Software Group Incorporated (RedPrairie Holding Incorporated)
• Inventors: Slocum, Gregory H., Iyer, Anand, Brigham, John D.
• Primary Examiner(s): Jeanty, Romain
• Assistant Examiner(s): CHONG CRUZ, NADJA N
• Application Number:
  US10/175,488
• Time in Patent Office: 4,136 Days
• Field of Search: 705/7, 705/7.12
• US Class Current: 705/7.12
• CPC Class Codes: G05B 15/02 electric
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

A method for continuous production planning includes identifying a forbidden transition associated with production of first and second end products. The forbidden transition indicates that a manufacturer should not produce the first and second end products consecutively. The method also includes identifying a bridge product associated with the forbidden transition. The bridge product represents a product that the manufacturer could produce between production of the first and second end products. The method further includes determining a quantity of the bridge product that could be produced by the manufacturer. In addition, the method includes scheduling production of the first and second end products and the bridge product. At least a portion of the quantity of the bridge product is scheduled for production between the production of the first and second end products.

Claims

1. A computer-implemented method of continuous production planning, comprising:

accessing, by a computer, a transition matrix comprising a plurality of transition values each associated with first and second end products;

identifying, by the computer, a forbidden transition associated with production of the first and second end products, the forbidden transition identifying an unusable transition product produced when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product;

identifying, by the computer, a bridge product associated with the forbidden transition, the bridge product representing a product to be manufactured between production of the first and second end products and selected based on one or more rules reflecting one or more user preferences, the one or more rules identifying criteria that identifies the bridge product;

determining, by the computer, a quantity of the bridge product to be manufactured by identifying an existing demand of the bridge product and an additional quantity of the bridge product to be produced by the production equipment; and

scheduling, by the computer, production of the first and second end products and the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

2. The method of claim 1, further comprising:

identifying an allowable transition associated with production of the first and second end products, the allowable transition indicating that the manufacturer may produce the first and second end products consecutively.

3. The method of claim 2, wherein identifying the bridge product associated with the forbidden transition comprises:

generating a graph associated with the transition matrix, the graph comprising a plurality of nodes each associated with the first and second products;

identifying a source node associated with the first end product and a destination node associated with the second end product; and

identifying any articulation points in the graph between the source and destination nodes, an articulation point identifying at least one bridge product associated with the forbidden transition.

4. The method of claim 3, wherein identifying the bridge product associated with the forbidden transition further comprises:

identifying an intermediate node associated with the first and second end products for which there is no existing demand;

determining whether the intermediate node also represents one of the articulation points; and

removing the intermediate node from the graph if the intermediate node does not represents an articulation point.

5. The method of claim 4, wherein identifying the bridge product associated with the forbidden transition further comprises identifying a shortest path between the source and destination nodes, the shortest path including one or more nodes in the graph, the one or more nodes forming the shortest path including any articulation points between the source and destination nodes, the one or more nodes identifying one or more bridge products.

6. The method of claim 5, wherein the shortest path comprises at least one of:

a first path involving a minimum amount of time needed to produce the one or more products associated with the one or more nodes forming the first path;

a second path involving a minimum number of one or more products that do not represent end products; and

a third path involving a minimum quantity of one or more products that do not represent end products.

7. The method of claim 5, wherein identifying the shortest path between the source and destination nodes comprises identifying the shortest path between the source and destination nodes using one or more business rules.

8. A computer-implemented method of continuous production planning, comprising:

accessing, by a computer, a transition matrix comprising a plurality of transition values each associated with first and second end products;

identifying, by the computer, a forbidden transition associated with production of the first and second end products, the forbidden transition identifying an unusable transition product produced when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product;

identifying, by the computer, a bridge product associated with the forbidden transition, the bridge product representing a product to be manufactured between production of the first and second end products;

determining, by the computer, a quantity of the bridge product to be manufactured by;

determining a demand quantity needed to satisfy existing demand for the bridge product;

determining a maximum quantity of the bridge product that the production equipment can produce;

comparing the demand quantity and the maximum quantity; and

determining an additional quantity of the bridge product that the production equipment can produce in addition to the demand quantity of the bridge product, the additional quantity equal to a difference between the demand quantity and the maximum quantity when the demand quantity is less than the maximum quantity, the additional quantity equal to zero when the demand quantity is not less than the maximum quantity; and

scheduling, by the computer, production of the first and second end products and the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

9. The method of claim 8, wherein scheduling production of the first and second end products and the bridge product comprises scheduling production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product.

10. The method of claim 9, wherein:

the method further comprises assigning a first priority value to the demand quantity and a second priority value to the additional quantity, the priority values indicating that the demand quantity has a higher importance than the additional quantity; and

scheduling production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product comprises scheduling production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product using the first and second priority levels.

11. The method of claim 10, wherein scheduling production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product using the first and second priority levels comprises scheduling production of all of the demand quantity of the bridge product and only a portion of the additional quantity of the bridge product.

12. The method of claim 8, wherein:

the first and second end products comprise two products of a plurality of products; and

determining the maximum quantity of the bridge product comprises;

identifying one or more pairs of end products associated with the bridge product;

determining a transition block time associated with each pair of end products;

identifying a number of time units in a planning horizon;

determining an upper bound associated with each pair of end products, the upper bound representing a number of lots of the bridge product that could be produced; and

determining a total number of lots of the bridge product using the upper bound associated with at least one pair of end products, the maximum quantity based on the total number of lots.

13. The method of claim 12, wherein:

one of the pairs of end products comprises a first product and a second product; and

the upper bound associated with the pair of end products comprises a minimum of;

a sum of a minimum production time of the first end product and a run time of one lot of the bridge product;

a sum of a minimum production time of the second end product and the run time of one lot of the bridge product; and

zero when there is no existing demand for at least one of the first and second end products.

14. The method of claim 12, wherein the total number of lots comprises one of a sum of the upper bounds over all pairs of end products and a maximum upper bound.

15. A system of continuous production planning, comprising:

memory accessing a transition matrix comprising a plurality of transition values each associated with first and second end products;

memory identifying a forbidden transition associated with production of the first and second end products, the forbidden transition identifying an unusable transition product produced when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product; and

one or more processors collectively configured to;

identify a bridge product associated with the forbidden transition, the bridge product representing a product to be manufactured between production of the first and second end products and selected based on one or more rules reflecting one or more user preferences, the one or more rules identifying criteria that identifies the bridge product;

determine a quantity of the bridge product to be manufactured by identifying an existing demand of the bridge product and an additional quantity of the bridge product to be produced by the production equipment; and

schedule production of the first and second end products and the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

16. The system of claim 15, wherein:

the one or more processors are collectively configured to identify an allowable transition associated with production of the first and second end products, the allowable transition indicating that the manufacturer may produce the first and second end products consecutively.

17. The system of claim 16, wherein the one or more processors are collectively configured to identify the bridge product associated with the forbidden transition by:

generating a graph associated with the transition matrix, the graph comprising a plurality of nodes each associated with the first and second products;

identifying a source node associated with the first end product and a destination node associated with the second end product; and

identifying any articulation points in the graph between the source and destination nodes, an articulation point identifying at least one bridge product associated with the forbidden transition.

18. The system of claim 17, wherein the one or more processors are further collectively configured to identify the bridge product associated with the forbidden transition further by:

identifying an intermediate node associated with the first and second end products for which there is no existing demand;

determining whether the intermediate node also represents one of the articulation points; and

removing the intermediate node from the graph if the intermediate node does not represents an articulation point.

19. The system of claim 18, wherein the one or more processors are further collectively configured to identify the bridge product associated with the forbidden transition further by identifying a shortest path between the source and destination nodes, the shortest path including one or more nodes in the graph, the one or more nodes forming the shortest path including any articulation points between the source and destination nodes, the one or more nodes identifying one or more bridge products.

20. The system of claim 19, wherein the shortest path comprises at least one of:

a first path involving a minimum amount of time needed to produce the one or more products associated with the one or more nodes forming the first path;

a second path involving a minimum number of one or more products that do not represent end products; and

a third path involving a minimum quantity of one or more products that do not represent end products.

21. The system of claim 19, wherein the one or more processors are collectively configured to identify the shortest path between the source and destination nodes using one or more business rules.

22. A system of continuous production planning, comprising:

memory accessing a transition matrix comprising a plurality of transition values each associated with first and second end products;

memory identifying a forbidden transition associated with production of the first and second end products, the forbidden transition identifying an unusable transition product produced when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product; and

one or more processors collectively configured to;

identify a bridge product associated with the forbidden transition, the bridge product representing a product to be manufactured between production of the first and second end products;

determine a quantity of the bridge product to be manufactured by;

determining a demand quantity needed to satisfy existing demand for the bridge product;

determining a maximum quantity of the bridge product that the production equipment can produce;

comparing the demand quantity and the maximum quantity; and

determining an additional quantity of the bridge product that the production equipment can produce in addition to the demand quantity of the bridge product, the additional quantity equal to a difference between the demand quantity and the maximum quantity when the demand quantity is less than the maximum quantity, the additional quantity equal to zero when the demand quantity is not less than the maximum quantity; and

schedule production of the first and second end products and the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

23. The system of claim 22, wherein the one or more processors are collectively configured to schedule production of the first and second end products and the bridge product by scheduling production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product.

24. The system of claim 23, wherein:

the one or more processors are further collectively configured to assign a first priority value to the demand quantity and a second priority value to the additional quantity, the priority values indicating that the demand quantity has a higher importance than the additional quantity; and

the one or more processors are collectively configured to schedule production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product using the first and second priority levels.

25. The system of claim 24, wherein the one or more processors are collectively configured to schedule production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product using the first and second priority levels by scheduling production of all of the demand quantity of the bridge product and only a portion of the additional quantity of the bridge product.

26. The system of claim 22, wherein:

the first and second end products comprise two products of a plurality of products; and

the one or more processors are collectively configured to determine the maximum quantity of the bridge product by;

identifying one or more pairs of end products associated with the bridge product;

determining a transition block time associated with each pair of end products;

identifying a number of time units in a planning horizon;

determining an upper bound associated with each pair of end products, the upper bound representing a number of lots of the bridge product that could be produced; and

determining a total number of lots of the bridge product using the upper bound associated with at least one pair of end products, the maximum quantity based on the total number of lots.

27. The system of claim 26, wherein:

one of the pairs of end products comprises a first product and a second product; and

the upper bound associated with the pair of end products comprises a minimum of;

a sum of a minimum production time of the first end product and a run time of one lot of the bridge product;

a sum of a minimum production time of the second end product and the run time of one lot of the bridge product; and

zero when there is no existing demand for at least one of the first and second end products.

28. The system of claim 26, wherein the total number of lots comprises one of a sum of the upper bounds over all pairs of end products and a maximum upper bound.

29. A non transitory computer-readable medium embodied with software for continuous production planning, the software when executed by one or more processors is configured to:

access a transition matrix comprising a plurality of transition values each associated with first and second end products;

identify a forbidden transition associated with production of the first and second end products, the forbidden transition identifying an unusable transition product when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product;

identify a bridge product associated with the forbidden transition, the bridge product representing a product to be manufactured between production of the first and second end products and selected based on one or more rules reflecting one or more user preferences, the one or more rules identifying criteria that identifies the bridge product;

determine a quantity of the bridge product to be manufactured by identifying an existing demand of the bridge product and an additional quantity of the bridge product to be produced by the production equipment; and

schedule production of the first and second end products and the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

30. A computer-implemented method of continuous production planning, comprising:

accessing, by a computer, a transition comprising a plurality of transition values each associated with first and second end products;

identifying, by the computer, a forbidden transition associated with production of the first and second end products using the transition matrix, the forbidden transition identifying an unusable transition product when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product, the transition matrix comprising a plurality of transition values each associated with two products of a plurality of products and identifying whether a transition between the two products of the plurality of products is allowable or forbidden, the plurality of products including the first and second end products;

identifying, by the computer, a bridge product associated with the forbidden transition by converting the transition matrix to a graph comprising a plurality of nodes each associated with one of the plurality of products and identifying a shortest path between a source node and a destination node in the graph, the source node associated with the first end product, the destination node associated with the second end product, the bridge product representing a product that the production equipment could produce between production of the first and second end products;

determining, by the computer, a demand quantity of the bridge product needed to satisfy existing demand for the bridge product;

determining, by the computer, an additional quantity of the bridge product that the production equipment can produce in addition to the demand quantity of the bridge product; and

scheduling, by the computer, production of quantities of the first and second end products and at least a portion of one or more of the demand quantity and the additional quantity of the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

31. A system of continuous production planning, comprising:

memory configured to store a transition matrix, the transition matrix comprising a plurality of transition values each associated with two products of a plurality of products and identifying whether a transition between the two products of the plurality of products is allowable or forbidden, the plurality of products including first and second end products; and

one or more processors collectively configured to;

identify a forbidden transition associated with production of the first and second end products using the transition matrix, the forbidden transition identifying an unusable transition product when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product;

identify a bridge product associated with the forbidden transition by converting the transition matrix to a graph comprising a plurality of nodes each associated with one of the plurality of products and identifying a shortest path between a source node and a destination node in the graph, the source node associated with the first end product, the destination node associated with the second end product, the bridge product representing a product that the production equipment could produce between production of the first and second end products;

determine a demand quantity of the bridge product needed to satisfy existing demand for the bridge product;

determine an additional quantity of the bridge product that the production equipment can produce in addition to the demand quantity of the bridge product; and

schedule production of quantities of the first and second end products and at least a portion of one or more of the demand quantity and the additional quantity of the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

32. A non transitory computer-readable medium embodied with software for continuous production planning, the software when executed by one or more processors is configured to:

access a transition matrix comprising a plurality of transition values each associated with first and second end products;

identify a forbidden transition associated with production of the first and second end products using the transition matrix, the forbidden transition identifying an unusable transition product when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product, the transition matrix comprising a plurality of transition values each associated with two products of a plurality of products and identifying whether a transition between the two products of the plurality of products is allowable or forbidden, the plurality of products including the first and second end products;

identify a bridge product associated with the forbidden transition by converting the transition matrix to a graph comprising a plurality of nodes each associated with one of the plurality of products and identifying a shortest path between a source node and a destination node in the graph, the source node associated with the first end product, the destination node associated with the second end product, the bridge product representing a product that the production equipment could produce between production of the first and second end products;

determine a demand quantity of the bridge product needed to satisfy existing demand for the bridge product;

determine an additional quantity of the bridge product that the production equipment can produce in addition to the demand quantity of the bridge product; and

schedule production of quantities of the first and second end products and at least a portion of one or more of the demand quantity and the additional quantity of the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

33. A non transitory computer-readable medium embodied with software for continuous production planning, the software when executed by one or more processors is configured to:

access a transition matrix comprising a plurality of transition values each associated with first and second end products;

identify a forbidden transition associated with production of the first and second end products, the forbidden transition identifying an unusable transition product when production equipment continues manufacturing a product while the production equipment is in the process of changing from manufacturing the first end product to manufacturing the second end product;

identify a bridge product associated with the forbidden transition, the bridge product representing a product to be manufactured between production of the first and second end products;

determine a quantity of the bridge product to be manufactured by;

determining a demand quantity needed to satisfy existing demand for the bridge product;

determining a maximum quantity of the bridge product that the production equipment can produce;

comparing the demand quantity and the maximum quantity; and

determining an additional quantity of the bridge product that the production equipment can produce in addition to the demand quantity of the bridge product, the additional quantity equal to a difference between the demand quantity and the maximum quantity when the demand quantity is less than the maximum quantity, the additional quantity equal to zero when the demand quantity is not less than the maximum quantity; and

schedule production of the first and second end products and the bridge product, wherein the bridge product is scheduled for production between the production of the first and second end products.

34. The computer-readable medium of claim 33, wherein the software is further configured to schedule production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product.

35. The computer-readable medium of claim 34, wherein the software is further configured to:

assign a first priority value to the demand quantity and a second priority value to the additional quantity, the priority values indicating that the demand quantity has a higher importance than the additional quantity; and

schedule production of one or more of the demand quantity of the bridge product and the additional quantity of the bridge product using the first and second priority levels.

36. The computer-readable medium of claim 35, wherein the software is further configured to schedule production of all of the demand quantity of the bridge product and only a portion of the additional quantity of the bridge product.

37. The computer-readable medium of claim 33, wherein:

the first and second end products comprise two products of a plurality of products; and

the software is further configured to;

identify one or more pairs of end products associated with the bridge product;

determine a transition block time associated with each pair of end products;

identify a number of time units in a planning horizon;

determine an upper bound associated with each pair of end products, the upper bound representing a number of lots of the bridge product that could be produced; and

determine a total number of lots of the bridge product using the upper bound associated with at least one pair of end products, the maximum quantity based on the total number of lots.

38. The computer-readable medium of claim 37, wherein:

one of the pairs of end products comprises a first product and a second product; and

the upper bound associated with the pair of end products comprises a minimum of;

a sum of a minimum production time of the first end product and a run time of one lot of the bridge product;

a sum of a minimum production time of the second end product and the run time of one lot of the bridge product; and

zero when there is no existing demand for at least one of the first and second end products.

39. The computer-readable medium of claim 37, wherein the total number of lots comprises one of a sum of the upper bounds over all pairs of end products and a maximum upper bound.