Collaborative batch aggregation and scheduling in a manufacturing environment

• US 6,836,689 B2
• Filed: 11/06/2003
• Issued: 12/28/2004
• Est. Priority Date: 03/07/2000
• Status: Expired due to Term

• Current Assignee: Blue Yonder Group, Inc. (Panasonic Holdings Corporation)
• Original Assignee: i2 Technologies US Incorporated (Panasonic Holdings Corporation)
• Inventors: Joslin, David E., Schmidt, Craig W., Walser, Joachim Paul
• Primary Examiner(s): Gandhi, Jayprakash N.
• Assistant Examiner(s): Garland, Steven R.
• Application Number:
  US10/704,080
• Publication Number:
  US 20040098155A1
• Time in Patent Office: 418 Days
• Field of Search: 700/97, 700/99, 700/100, 700/106, 700/102, 700/28, 700/101, 700/103, 705/7, 705/8
• US Class Current: 700/100
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

In one aspect, a computer-implemented method is provided for aggregating and scheduling product batches in a manufacturing environment. Using a batch aggregation engine implementing a mathematical programming strategy, one or more product demands are allocated to one or more product batches having suggested sizes and suggested starting times. The mathematical programming strategy includes evaluating a number of time-based penalties relative to one another in allocating the demands to the batches, the time-based penalties being based on relationships between suggested starting times for batches and times of demands being considered for allocation to batches. The suggested sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times are communicated from the batch aggregation engine to a scheduling engine to assist the scheduling engine in scheduling starting times for the batches.

Claims

1. A computer-implemented method for aggregating and scheduling product batches in a manufacturing environment, comprising:

using a batch aggregation engine implementing a mathematical programming strategy, allocating one or more product demands to one or more product batches having suggested sizes and suggested starting times, the mathematical programming strategy comprising evaluating a plurality of time-based penalties relative to one another in allocating the demands to the batches, the time-based penalties being based on relationships between suggested starting times for batches and times of demands being considered for allocation to batches; and

communicating the suggested sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times from the batch aggregation engine to a scheduling engine to assist the scheduling engine in scheduling starting times for the batches.

2. The method of claim 1, wherein the mathematical programming strategy comprises a mixed-integer linear programming (MILP) strategy.

3. The method of claim 1, wherein the mathematical programming strategy comprises selecting a suggested size for each batch from among a plurality of discrete batch sizes.

4. The method of claim 1, wherein at least one time-based penalty comprises a hard constraint.

5. The method of claim 1, wherein the feedback communicated from the batch aggregation engine to the scheduling engine comprises one or more penalties associated with deviating from at least one of the suggested sizes or at least one of the suggested starting times.

6. The method of claim 5, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is a lateness penalty based on scheduling a starting time for a batch later than a demand allocated to the batch.

7. The method of claim 5, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of a shortage of a product.

8. The method of claim 5, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of a product inventory.

9. The method of claim 5, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of using a single batch to meet a demand for two or more product packaging sizes.

10. The method of claim 5, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of partially utilizing a shipping pallet to meet a demand.

11. The method of claim 5, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of partially using the available capacity of a piece of manufacturing equipment.

12. The method of claim 1, wherein the feedback communicated from the batch aggregation engine to the scheduling engine comprises a penalty table including one or more penalties for each suggested starting time and associated with starting a batch of the suggested size at the corresponding suggested starting time.

13. The method of claim 12, wherein a plurality of suggested batches are communicated from the batch aggregation engine to the scheduling engine, each batch having an associated penalty table.

14. The method of claim 1, further comprising:

using the scheduling engine, scheduling starting times for the batches according to the suggested sizes, suggested starting times, and associated feedback received from the batch aggregation engine; and

communicating the scheduled starting times and feedback relating to the scheduled starting times from the scheduling engine to the batch aggregation engine to assist the batch aggregation engine, implementing the mathematical programming strategy, in re-allocating one or more demands to one or more batches according to the scheduled starting times and associated feedback received from the scheduling engine.

15. The method of claim 14, wherein scheduling a starting time comprises scheduling a starting time on a particular resource.

16. The method of claim 14, wherein scheduling a starting time comprises scheduling a starting time for a batch having a size not suggested by the batch aggregation engine.

17. The method of claim 14, wherein the feedback communicated from the scheduling engine to the batch aggregation engine comprises one or more time-based penalties associated with deviating from at least one of the scheduled starting times.

18. The method of claim 17, wherein at least one penalty within the feedback communicated from the scheduling engine to the batch aggregation engine is based on a capacity of all available product manufacturing equipment according to a required production of a plurality of different product types.

19. The method of claim 17, wherein at least one penalty within the feedback communicated from the scheduling engine to the batch aggregation engine is based on an individual capacity of a piece of manufacturing equipment.

20. The method of claim 17, wherein at least one penalty within the feedback communicated from the scheduling engine to the batch aggregation engine is based on a changeover time associated with changing a type of product manufactured in a particular piece of manufacturing equipment.

21. The method of claim 14, wherein the steps are repeated in an iterative cycle until the batch aggregation engine and the scheduling engine collaboratively reach a sufficiently optimal batch aggregation and scheduling solution or until a predetermined number of iterations has been reached.

22. The method of claim 21, wherein the feedback communicated from the batch aggregation engine to the scheduling engine comprises one or more penalties, associated with deviating from at least one of the suggested starting times or at least one of the suggested sizes, that increase for each iteration in the iterative cycle.

23. The method of claim 21, wherein the feedback communicated from the scheduling engine to the batch aggregation engine comprises one or more penalties, associated with deviating from at least one of the scheduled starting times, that increase for each iteration in the iterative cycle.

24. The method of claim 14, wherein:

allocating demands to batches comprises allocating one or more demands for a first product to one or more batches of the first product and allocating one or more demands for a second product to one or more batches of the second product; and

scheduling starting times for one or more of the batches comprises scheduling a starting time for one or more batches of each of the first and second products.

25. The method of claim 24, wherein the batches of the first and second products are scheduled such that the batches may be manufactured using the same manufacturing equipment.

26. The method of claim 1, wherein allocating demands to batches comprises aggregating a plurality of demands into one or more batches.

27. The method of claim 1, wherein allocating demands to batches comprises splitting a demand into a plurality of batches.

28. The method of claim 1, wherein allocating demands to batches comprises allocating one or more demands for a partially manufactured product from a previous stage in a manufacturing process to one or more batches.

29. A computer-based system for aggregating and scheduling product batches in a manufacturing environment, comprising a batch aggregation engine operable to:

allocate one or more product demands to one or more product batches having suggested sizes and suggested starting times according to a mathematical programming strategy, the mathematical programming strategy comprising evaluating a plurality of time-based penalties relative to one another in allocating the demands to the batches, the time-based penalties being based on relationships between suggested starting times for batches and times of demands being considered for allocation to batches; and

communicate the suggested batch sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times from the batch aggregation engine to a scheduling engine to assist the scheduling engine in scheduling starting times for the batches.

30. The system of claim 29, wherein the mathematical programming strategy comprises a mixed-integer linear programming (MILP) strategy.

31. The system of claim 29, wherein the mathematical programming strategy comprises selecting a suggested size for each batch from among a plurality of discrete batch sizes.

32. The system of claim 29, wherein at least one time-based penalty comprises a hard constraint.

33. The system of claim 29, wherein the feedback communicated from the batch aggregation engine to the scheduling engine comprises one or more penalties associated with deviating from at least one of the suggested sizes or at least one of the suggested starting times.

34. The system of claim 33, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is a lateness penalty based on scheduling a starting time for a batch later than a demand allocated to the batch.

35. The system of claim 33, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of a shortage of a product.

36. The system of claim 33, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of a product inventory.

37. The system of claim 33, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of using a single batch to meet a demand for two or more product packaging sizes.

38. The system of claim 33, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of partially utilizing a shipping pallet to meet a demand.

39. The system of claim 33, wherein at least one penalty within the feedback communicated from the batch aggregation engine to the scheduling engine is based on a cost of partially using the available capacity of a piece of manufacturing equipment.

40. The system of claim 29, wherein the feedback communicated from the batch aggregation engine to the scheduling engine comprises a penalty table including one or more penalties for each suggested starting time, each penalty associated with starting a batch of the suggested size at the corresponding suggested time.

41. The system of claim 40, wherein the batch aggregation engine is operable to communicate a plurality of suggested batches to the scheduling engine, each batch having an associated penalty table.

42. The system of claim 29, further comprising the scheduling engine coupled to the batch aggregation engine, the scheduling engine operable to:

receive the suggested sizes, suggested starting times, and feedback from the batch aggregation engine;

schedule starting times for the batches according to the suggested sizes, suggested starting times, and feedback received from the batch aggregation engine; and

communicate the scheduled starting times and feedback relating to the scheduled starting times to the batch aggregation engine to assist the batch aggregation engine, implementing the mathematical programming strategy, in re-allocating one or more demands to one or more batches according to the scheduled starting times and associated feedback received from the scheduling engine.

43. The system of claim 42, wherein the scheduling engine is operable to schedule a starting time of a batch on a particular resource.

44. The system of claim 42, wherein the scheduling engine is operable to schedule a starting time for a batch having a size not suggested by the batch aggregation engine.

45. The system of claim 42, wherein the feedback communicated from the scheduling engine to the batch aggregation engine comprises one or more time-based penalties associated with deviating from at least one of scheduled starting times.

46. The system of claim 45, wherein at least one penalty within the feedback communicated from the scheduling engine to the batch aggregation engine is based on a capacity of all available product manufacturing equipment according to a required production of a plurality of different product types.

47. The system of claim 45, wherein at least one penalty within the feedback communicated from the scheduling engine to the batch aggregation engine is based on an individual capacity of a piece of manufacturing equipment.

48. The system of claim 45, wherein at least one penalty within the feedback communicated from the scheduling engine to the batch aggregation engine is based on a changeover time associated with changing a type of product manufactured in a particular piece of product manufacturing equipment.

49. The system of claim 42, wherein the batch aggregation engine and the scheduling engine are further operable to communicate their respective outputs to each other in an iterative cycle until they collaboratively reach a sufficiently optimal batch aggregation and scheduling solution or until a predetermined number of iterations has been reached.

50. The system of claim 49, wherein the feedback communicated from the batch aggregation engine to the scheduling engine comprises one or more penalties, associated with deviating from at least one of the suggested sizes or at least one of the suggested starting times, that increase for each iteration in the iterative cycle.

51. The system of claim 49, wherein the feedback communicated from the scheduling engine to the batch aggregation engine comprises one or more penalties, associated with deviating from at least one of the scheduled starting times, that increase for each iteration in the iterative cycle.

52. The system of claim 42, wherein:

the batch aggregation engine is operable to allocate demands for a first product to batches of the first product and operable to allocate demands for a second product to batches of the second product; and

the scheduling engine is operable to schedule starting times for one or more batches of each of the first and second products.

53. The system of claim 52, wherein the scheduling engine is operable to schedule the batches of the first and second products such that the batches may be manufactured using the same manufacturing equipment.

54. The system of claim 29, wherein the batch aggregation engine is operable to allocate demands for a partially manufactured product from a previous stage in a manufacturing process into one or more batches.

55. Computer software for aggregating and scheduling product batches in a manufacturing environment, the software embodied in one or more computer-readable media, the software comprising batch aggregation software operable when executed to:

allocate one or more product demands to one or more product batches having suggested sizes and suggested starting times according to a mathematical programming strategy, the mathematical programming strategy comprising evaluating a plurality of time-based penalties relative to one another in allocating the demands to the batches, the time-based penalties being based on relationships between suggested starting times for batches and times of demands being considered for allocation to batches; and

communicate the suggested sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times from the batch aggregation software to scheduling software to assist the scheduling software in scheduling starting times for the batches.

56. The software of claim 55, wherein the mathematical programming strategy comprises a mixed-integer linear programming (MILP) strategy.

57. The software of claim 55, wherein the mathematical programming strategy comprises selecting a suggested size for each batch from among a plurality of discrete batch sizes.

58. The software of claim 55, wherein at least one time-based penalty comprises a hard constraint.

59. The software of claim 55, wherein the feedback communicated from the batch aggregation software to the scheduling software comprises one or more penalties associated with deviating from at least one of the suggested sizes or at least one of the suggested starting times.

60. The software of claim 59, wherein at least one penalty within the feedback communicated from the batch aggregation software to the scheduling software is a lateness penalty based on scheduling a starting time for a batch later than a demand allocated to the batch.

61. The software of claim 59, wherein at least one penalty within the feedback communicated from the batch aggregation software to the scheduling software is based on a cost of a shortage of a product.

62. The software of claim 59, wherein at least one penalty within the feedback communicated from the batch aggregation software to the scheduling software is based on a cost of a product inventory.

63. The software of claim 59, wherein at least one penalty within the feedback communicated from the batch aggregation software to the scheduling software is based on a cost of using a single batch to meet a demand for two or more product packaging sizes.

64. The software of claim 59, wherein at least one penalty within the feedback communicated from the batch aggregation software to the scheduling software is based on a cost of partially utilizing a shipping pallet to meet a demand.

65. The software of claim 59, wherein at least one penalty within the feedback communicated from the batch aggregation software to the scheduling software is based on a cost of partially using the available capacity of a piece of manufacturing equipment.

66. The software of claim 55, wherein the feedback communicated from the batch aggregation software to the scheduling software comprises a penalty table including one or more penalties for each suggested starting time and associated with starting a batch of the suggested size at the corresponding suggested starting time.

67. The software of claim 66, wherein a plurality of suggested batches are communicated from the batch aggregation software to the scheduling software, each batch having an associated penalty table.

68. The software of claim 55, further comprising the schedule software, operable when executed to:

schedule starting times for the batches according to the suggested sizes, suggested starting times, and associated feedback received from the batch aggregation software; and

communicate the scheduled starting times and feedback relating to the scheduled starting times from the scheduling software to the batch aggregation software to assist the batch aggregation software, implementing the mathematical programming strategy, in re-allocating one or more demands to one or more batches according to the scheduled starting times and associated feedback received from the scheduling software.

69. The software of claim 68, wherein scheduling a starting time comprises scheduling a starting time on a particular resource.

70. The software of claim 68, wherein scheduling a starting time comprises scheduling a starting time for a batch having a size not suggested by the batch aggregation software.

71. The software of claim 68, wherein the feedback communicated from the scheduling software to the batch aggregation software comprises one or more time-based penalties associated with deviating from at least one of the scheduled starting times.

72. The software of claim 71, wherein at least one penalty within the feedback communicated from the scheduling software to the batch aggregation software is based on a capacity of all available product manufacturing equipment according to a required production of a plurality of different product types.

73. The software of claim 71, wherein at least one penalty within the feedback communicated from the scheduling software to the batch aggregation software is based on an individual capacity of a piece of manufacturing equipment.

74. The software of claim 71, wherein at least one penalty within the feedback communicated from the scheduling software to the batch aggregation software is based on a changeover time associated with changing a type of product manufactured in a particular piece of manufacturing equipment.

75. The software of claim 68, wherein the steps are repeated in an iterative cycle until the batch aggregation software and the scheduling software collaboratively reach a sufficiently optimal batch aggregation and scheduling solution or until a predetermined number of iterations has been reached.

76. The software of claim 75, wherein the feedback communicated from the batch aggregation software to the scheduling software comprises one or more penalties, associated with deviating from at least one of the suggested sizes or at least one of the suggested starting times, that increase for each iteration in the iterative cycle.

77. The software of claim 75, wherein the feedback communicated from the scheduling software to the batch aggregation software comprises one or more penalties, associated with deviating from at least one of the scheduled starting times, that increase for each iteration in the iterative cycle.

78. The software of claim 68, wherein:

allocating demands to batches comprises allocating one or more demands for a first product to one or more batches of the first product and allocating one or more demands for a second product to one or more batches of the second product; and

scheduling a starting time for one or more batches comprises scheduling a starting time for one or more of the batches of each of the first and second products.

79. The software of claim 78, wherein the batches of the first and second products are scheduled such that the batches may be manufactured using the same manufacturing equipment.

80. The software of claim 55, wherein allocating demands to batches comprises aggregating a plurality of demands into one or more batches.

81. The software of claim 55, wherein allocating demands to batches comprises splitting a demand into a plurality of batches.

82. The software of claim 55, wherein allocating demands to batches comprises allocating one or more demands for a partially manufactured product from a previous stage in a manufacturing process to one or more batches.

83. A system for aggregating and scheduling product batches in a manufacturing environment, comprising:

batch aggregation means for allocating one or more product demands to one or more product batches having suggested sizes and suggested starting times according to a mathematical programming strategy, the mathematical programming strategy comprising evaluating a plurality of time-based penalties relative to one another in allocating the demands to the batches, the time-based penalties being based on relationships between suggested starting times for batches and times of demands being considered for allocation to batches; and

communication means for communicating the suggested sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times from the batch aggregation means to scheduling means for scheduling starting times for batches to assist the scheduling means in scheduling starting times for the batches.

84. A method for aggregating and scheduling product batches in a manufacturing environment, comprising:

using a batch aggregation engine implementing a mixed-integer linear programming (MILP) strategy, allocating one or more product demands to one or more product batches having suggested sizes and suggested starting times, the MILP strategy comprising evaluating a plurality of time-based penalties relative to one another in allocating the demands to the batches, the time-based penalties being based on relationships between suggested starting times for batches and times of demands being considered for allocation to batches; and

communicating the suggested sizes, the suggested starting times, and feedback relating to the suggested sizes and suggested starting times from the batch aggregation engine to a scheduling engine to assist the scheduling engine in scheduling starting times for the batches, the feedback communicated from the batch aggregation engine to the scheduling engine comprising one or more penalties associated with deviating from at least one of the suggested sizes or at least one of the suggested starting times;

using the scheduling engine, scheduling starting times for the batches according to the suggested sizes, suggested starting times, and associated feedback received from the batch aggregation engine; and

communicating the scheduled starting times and feedback relating to the scheduled starting times from the scheduling engine to the batch aggregation engine to assist the batch aggregation engine, implementing the MILP strategy, in re-allocating one or more demands to one or more batches according to the scheduled starting times and associated feedback received from the scheduling engine, the feedback communicated from the scheduling engine to the batch aggregation engine comprising one or more time-based penalties associated with deviating from at least one of the scheduled starting times; and

repeating the above steps in an iterative cycle until the batch aggregation engine and the scheduling engine collaboratively reach a sufficiently optimal batch aggregation and scheduling solution or until a predetermined number of iterations has been reached.