Data processing: generic control systems or specific application – Specific application – apparatus or process – Article handling
Reexamination Certificate
2000-07-25
2001-11-20
Ellis, Christopher P. (Department: 3651)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Article handling
C198S358000, C198S418100
Reexamination Certificate
active
06321135
ABSTRACT:
BACKGROUND
1. Field of the Invention
This invention relates to batching items, e.g., based on weight or other characteristics of the items. The batching of items is sometimes referred to as “the on-line bin-packing problem.” More specifically, this invention relates to the problem of accumulation of non-uniform items forming a best possible uniformity of the accumulated batch.
2. Background
In various industries, basic items are sold in batches satisfying various constraints. For example, many food items (such as, e.g., fresh or frozen fish portions, chicken portions and the like) are sold in prepackaged batches having a predetermined weight and/or number of pieces, within given tolerances. The tolerances may be quite strict in some industries.
Batching has developed as a result of contracts between sellers and purchasers for delivery of products which must satisfy minimum weight or other requirements. It is very important that none of the collections be below minimum weight but exceeding this weight results in an economical loss for the manufacturer, has impact on the transportation costs, taxation fees etc.
Various statistical methods have been suggested for solving the problem of reaching the batch size with as little overweight as possible. E.g., some prior art teaches the use of equations for a normal distribution or similar use of algorithms based on weight distributions. Such methods have disadvantages in that they are often difficult to apply, use large amounts of computer memory and use large computer processing resources each time an item is to be assigned to a batch.
One way to overcome the difficulties with these known methods is to omit updating all sets of data when an item is assigned to a batch. However, a major drawback of omitting updating of the sets of data is that changes in the population of items are not captured by these methods and these methods may then be based on wrong, or at least inaccurate, statistical data, whereby the batching by these methods will be less optimal.
The omission of data may have a large influence on the batching process where, for instance, the distribution of items which initially follows a normal distribution then changes and follows another distribution. Such a situation may occur if items having a special characteristic temporarily are assigned to special processing.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide useful, fast and efficient methods, systems and devices for batching items, so that the processing involved in the batching will not limit the batching capacity and wherein the data used in the batching process may be updated each time an item is assigned to a batch.
The present invention is preferably based on a so-called Tally Intelligent Batching Algorithm (or Tally Algorithm). The tally is preferably the total number of possible combinations of items present in a First-In-First-Out (“FIFO”) queue as a function of batch shortage and item count. This is significantly different from prior art's use of the weight distribution.
In one aspect, the present invention provides a method for generating a prospect for filling a batch with at least one item having at least one characteristic property, where the prospect is used for assigning an item to a batch having at least one batch shortage expressed in terms of the at least one characteristic property. In some embodiments, the method comprises:
(a) Providing a first set of data representing at least one characteristic property of at least one item.
(b) Providing a second set of data representing at least one batch shortage.
(c) Generating a third set of data representing a tally on the number of combinations of the items represented in the first set of data as a function of batch shortage and item count. This tally may be kept for all relevant batch shortages and numbers of items.
(d) Providing a fourth set of data indicating at least one batch shortage and an optionally maximum number of items on which the prospect generation is to be based.
(e) Generating the prospect related to the fourth set of data on the basis of multiplying each of the entries of the third set of data by the single count probability corresponding to each entry subject to the proviso that each of the entries multiplied represents
one of the batch shortages indicated in the fourth set of data, and
a number of combinations of items being smaller than or equal to the provided maximum number of items.
A number of terms are used which are commonly used in the batching and statistical literature. An explanation of some of the special terms and concepts relevant to the present invention are given here:
Batch:
A collection of items (may, of course, comprise only one item)
Batch Shortage:
The amount, for instance expressed in kilograms, that should be placed in a particular batch in order for that batch to fulfill a predetermined batch size.
Batch Size:
The amount, for instance expressed in kilograms, contained in a batch.
Prospect:
Having a collection of items where each item has been assigned a characteristic property, such as the weight of the item, and at least one batch to be filled with a number of items, then by test-fitting or placing one or more items into the batch the prospect is a measure for the probability of being able to get another item or a combination of items having a characteristic property substantially equal to the batch shortage resulting from test-fitting or placing the one or more items into the batch.
Test-fitting:
Fictively placing an item in a batch.
Prospect Change:
The change in the prospect of a batch when an item is test-fitted in the batch. There are many possible ways to calculate the prospect change, the only requirement being that the prospect change is increases with the prospect of the batch with the new item test-fitted.
Number of Combinations
Having a collection of items, where each item has been assigned a characteristic property, such as the weight of the item, and a batch shortage, then counting the number of different combinations of a fixed number of items whose characteristic properties sum to the batch shortage.
Single Count Probability:
The probability of drawing a single combination of a predefined number of items from a collection of items. This is calculated by the well-known formula for binomial coefficients, and depends on the following two quantities:
(1) The number of items in the collection of items; and
(2) The predefined number of items to be drawn from the bigger collection of items.
The processing (a)-(c) of the method according to the present invention relates to the generation of the Tally-matrix, and therefore may preferably not be executed each time a prospect is generated.
The batch shortage expressed in terms of at least one characteristic property may, in general, be expressed by any detectable and/or measurable unit such as grams, weight number of pieces, color etc., and combinations thereof. It is quite often preferred that, for instance, the weight of a batch and the number of items in the batch fulfill certain requirements and the present invention may, by generating a prospect for such a situation, be able to grade items so that such requirements are fulfilled.
One such situation may be described by the following example, which is only intended to assist in understanding the term “at least one batch shortage.” If the present invention is applied for making batches of, e.g., 400 g, and, , if the batches are allowed 10 g of overweight and the step between batch weights is 1 g, the method may try to make 400, 401, 402 . . . 410 g batches. In such a situation, the batch requirement may include the number of items to be used, i.e., a batch may/must be of 400 g (−0 g; +10 g) and comprise 3 (0; +1) pieces. That is, a batch must weigh between 400 g and 410 g and must comprise 3 or 4 pieces.
If a batch in such a situation weighs 390 g and comprises 2 items, the batch shortages relating to the weight may then be expressed as 400 g−390 g=10 g, 401 g−390 g=11 g, . . . 4
Ellis Christopher P.
Marel hf
Pillsbury & Winthrop LLP
Tran Khoi H.
LandOfFree
Batching of objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Batching of objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Batching of objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2570315