Abstract:
A combinatorial weighing method in a combinatorial weighing apparatus comprises the steps of providing two groups of patterns of combinations of weight values issued from a plurality of weighing machines, one of the groups is divided into two subgroups which are complements of each other, and the two groups are successively processed independently and in combination to find an optimum weight combination closest to a target weight value.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to a method of combinatorial weighing in a combinatorial weighing machine, and more particularly to a combinatorial weighing method capable of shortening a processing time for determining an optimum combination by improving patterns of weight combinations. 
     There is known a combinatorial weighing apparatus having a plurality of weighing machines for measuring the weights of articles therein. The combinatorial weighing apparatus operates by combining the weights from the weighing machines, finding a combination of weights which is equal to a target combination or closest to the target combination within an allowable preset range, discharging articles from the weighing machines which give such a combination found, then charging new articles into the emptied weighing machines, combining the weights from the weighing machines, and repeating the above process for successive automatic weighing operations. 
     FIG. 1 of the accompanying drawings schematically shows a combinatorial weighing apparatus for effecting such a combinatorial weighing operation. The apparatus includes a distribution table 11 for distributing articles radially outwardly to charge them into a plurality of n weighing sections 1, 1, . . . , 1 arranged radially and circumferentially spaced around the table 11. The distribution table 11 has a vibratory feeding capability and vibrates for a given interval of time for supplying the articles into the weighing sections. Each of the n weighing sections 1 has a weighing machine 101 comprising a distributive supply unit 1a, a pool hopper 1b, a pool hopper gate 1c, a hopper driver 1g, a weighing hopper 1d, and a weight detector 1e. The distributive supply units 1a are radially mounted on a support table 1h in circumferentially surrounding relation to the distribution table 11, and each distributive supply unit 1a has an electromagnetic vibrator 1a-1 and a trough 1a-2. Articles supplied from the distribution table 1a-1 to the trough 1a-2 are charged from a distal end of the trough 1a-2 into the pool hopper 1b by linear reciprocable movement of the electromagnetic vibrator 1a-1. The articles charged in each pool hopper 1b are then charged into the weighing hopper 1d when the hopper gate 1c is opened under the control of the hopper driver 1g. The articles charged in each weighing hopper 1d are measured for their weight by the associated weight detector 1e. The weight of the articles as measured by the weight detector 1e is applied as an input to a combinatorial processor unit, described below. The combinatorial processor unit effects combinatorial weighing processing on the weights to find an optimum combination of weights. The weighing hoppers 1d  of the weighing machines selected as giving the optimum combination are emptied to discharge the articles by opening the weighing hopper gates 1f by means of the hopper drivers 1g. The articles discharged from the weighing hoppers 1d fall into a collection chute 1j disposed below the weighing hoppers 1d, and are collected and delivered to a packaging machine (not shown). The collection chute 1j has a conical shape or a polygonal funnel shape. The articles are collected in the collection chute 1j by gravity or forcibly by a scraper (not shown) so that the articles will be gathered from an inner peripheral surface of the collection chute 1j toward a lower central position therein. 
     FIG. 2 is a block diagram of the combinatorial weighing apparatus. The combinatorial weighing apparatus includes n weighing machines 101-1, . . . , 101-n each composed of the weighing hopper 1d and the weight detector 1e, described above, for weighing the weights of supplied articles and issuing weight values Wi (i=1, 2, . . . , n). A multiplexer 102 issues the weight values Wi from the weighing machines 101-1, . . . , 101-n successively as a weight readout signal WRS, the multiplexer 102 being composed of analog switches and the like. The analog weight values Wi issued from the multiplexer 102 are converted into digital values by an A/D converter 103. A combinatorial weighing processor unit 104, in the form of a computer, basically includes a processor (central processing unit) 104a, a data memory 104b comprising a RAM, and a program memory 104c for storing a program for combinatorial processing. The processor 104a has a general-purpose register 104d. To the combinatorial weighing processor unit 104 are connected a weight setting unit 105 for setting a target weight value, upper and lower limit setting units 106, 107 for setting a preferable allowable preset range of combinatorial total weights, a display unit 108 for displaying a combinatorial total weight, selected weighing machines, weighing failures, and other information, and a discharge control unit 109. 
     Weighing operation of the combinatorial weighing apparatus shown in FIG. 2 will be described with reference to the flowchart of FIG. 3 and FIG. 4. 
     (1) When a start signal (timing signal) STS is generated by the packaging machine (not shown), the start signal STS is read by the processor 104a which then starts a combinatorial weighing process. 
     (2) Then, the processor 104a issues a weight readout signal WRS to the multiplexer 102 to enable the multiplexer 102 to apply the weight values Wi (i=1, 2, . . . , n) successively to the A/D converter 103. The weight values Wi applied to the A/D converter, are then converted thereby into digital signals which are fed to the combinatorial control unit 104, wherein the digital signals are stored by the processor 104a into the data memory 104b. 
     (3) Thereafter, the processor 104a effects 2 n  -1  combinatorial computations under the control of the combinatorial processing program. Where there are ten weighing machines, it has been conventional practice to combine detected weight data items from the ten weighing machines in group B composed of 1st through 8th weighing machines and in group A composed of 9th and 10th weighing machines as shown in FIG. 4. Since n=8 in group B, there are 2 8  -1=255 combinations. With such combination patterns, the general-purpose register 104d in the processor 104a has a 1st bit allotted to the 1st weighing machine 101-1, a 2nd bit to the 2nd weighing machine 101-2, . . . , an nth bit to the nth weighing machine 101-n, and the general-purpose register 104d counts from 1 up to 2 n  -1 to find 2 n  -1 combinations from 0000 . . . 001 to 1111 . . . 111. 
     In FIG. 4, the symbol W i  indicates ith data given by a combination of a elements. According to this definition, W 1 , for example, is indicative of a 1st added weight (combinatorial total weight) out of all combinations of eight weight data items (W 1 , W 2 , . . . , W 8 ), and is equal to W 1 . As another example, W 255  =W 1  +W 2  + . . . W 8 . 
     (4) FIG. 3 is a flowchart of a subroutine for determining one added weight (combinatorial total weight). This subroutine is executed each time one combinatorial pattern is generated. At the time of starting the subroutine, the added weight value is set to SUM=0 in a step b. Then, the processor 104a sets the numeral k stored in the data memory 104b to &#34;1&#34; in a step c. 
     (5) The processor 104a then checks bits of selected and non-selected weighing machines in a combinatorial pattern, that is, checks whether the kth bit in a combinatorial pattern is &#34;1&#34; or &#34;0&#34; in a step d. 
     (6) The processor 104a adds a weight value corresponding to a &#34;1&#34; bit in a combinatorial pattern to an added weight SUM in a step e. 
     (7) The processor 104a successively updates the numerical value k and repeats bit checking and weight addition until k&gt;8 in steps d, e, f, g. 
     (8) The above process will be described on the basis of specific numerals with reference to FIG. 4. The processor 104a first computes all combinatorial total weight data items (W 1 , W 2 , . . . , W 255 ) expressed in group B, and stores the data items in the data memory 104b. Then, the processor 104a adds the data items in group B and the data items in group A to find an optimum value closest to a target weight value. Since W 0  =0 in group A, three combinations (W 1 , W 2 , W 3 ) may be added to the combinations of group B. Such computations are effected by the combinatorial processor unit 104 as follows: 
     (1) Bit checking in combinatorial pattern: 
     Bit checking between selected and non-selected weighing machines is effected 8 times each time the subroutine of FIG. 3 is executed once. The subroutine of FIG. 3 is executed as many times as there are combinations of the eight weighing machines. Therefore, the total number of bit checking occurrences is 8×255=2040 . . . (i) 
     (2) Number of weight additions: 
     For selecting one out of eight weighing machines, there are 8 combinations, since  8  C 1  =8. The number of weight additions required in this case is 8×1=8. 
     For selecting two out of eight weighing machines, there are 28 combinations since  8  C 2  =28. The number of weight additions required is 28×2=56 since two additions need to be made for each combination. It follows therefore that the number of weight additions required for all combinations (255) in selecting one to eight weighing machines is given by: ##EQU1## 
     Furthermore, one addition is required to compute W 3  in group A (for adding the weights from the 10th and 9th weighing machines), and 3×255=765 additions are required to be made between groups A and B. Therefore, the total number of weight additions is: 
     
         1024+1+765=1790                                            . . . (iii) 
    
     The combinatorial processor unit 104 selects a combination closest to the target weight value, out of the combinatorial total weights thus produced, and controls the discharge control unit 109 to discharge the articles from the weighing machines which give such an optimum combination of weights. Therafter, the combinatorial processor unit 104 controls the pool hoppers to supply articles to the emptied weighing machines, and then waits for a next start signal from the packaging machine. 
     The process of determining an optimum weight combination using conventional combination patterns has suffered from a low processing speed since a great number of computations are necessary for bit checking and weight additions. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide a method of combinatorial weighing in a combinatorial weighing apparatus, wherein the time required for computations to find an optimum weight combination can be shortened by improving weight combination patterns to reduce the number of computations for bit checking and weight additions in a combinatorial processor unit. 
     According to the present invention, there is provided a method of combinatorial weighing in a combinatorial weighing apparatus including a plurality of weighing machines for determining the weights of charged articles, and a combinatorial processor unit for computing combinations of weight values issued from the weighing machines and for determining an optimum weight combination equal to a target weight value or closest to the target weight value within an allowable preset range. The method comprises the steps of providing two groups of patterns of combinations of the weight values, dividing one of the groups into two subgroups which are complements of each other, and successively processing the two groups independently and in combination to find the optimum weight combination. 
     The above and other objects, features and advantages of the present invention will become more apparent from the following description when taken in conjunction with the accompanying drawings in which preferred embodiments of the present invention are shown by way of illustrative example. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic side elevational view of a combinatorial weighing apparatus in which the method of the present invention can be effected; 
     FIG. 2 is a block diagram of the combinatorial weighing apparatus; 
     FIG. 3 is a flowchart for the successive steps of computing a combinatorial total weight; 
     FIG. 4 is a diagram of conventional patterns of combinations of weight data items; 
     FIGS. 5 and 6 are diagrams of patterns of combinations of weight data items, used to explain the method of the present invention; 
     FIG. 7 is a diagram of patterns of combinations of weight data items according to an embodiment of the present invention; 
     FIG. 8 is a diagram of patterns of combinations of weight data items according to another embodiment of the present invention; 
     FIG. 9 is a diagram of combination patterns generated by the method of the present invention as they are stored in a memory; and 
     FIG. 10 is a flowchart for the successive steps of combinatorial computation according to the present invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     A combinatorial weighing method according to the present invention will be described in greater detail with reference to the drawings. 
     (I) Pattern 1: 
     FIG. 5 is illustrative of patterns of weight combinations which serve as a basis for the present invention. The illustrated weight combination patterns are stored in a memory as two sets or group A (W 1  -W 511 ) and group B (W 512  -W 1022 ) into which combinatorial total weight data items are divided. Bits which are all &#34;1&#34; are stored as group C. With the two sets divided as groups A and B, the set B is expressed as a complement of the set A. More specifically, since W 10  is a whole set, the set B is expressed as: 
     
         B=A=W.sup.10 -A                                            . . . (1) 
    
     Since the set B can be found from the equation (1) by effecting computations to find combinatorial total weights of the set A only, and combinatorial computations for the set B may be omitted. 
     Therefore, the number of steps required for the computations is as follows: 
     (1) Bit checking: 
     Since the set of group B is a complement of the set of group A, bit checking may be effected with respect to group A only. Only 9 bits are checked as there is no bit of &#34;1&#34; for the 10th weighing machine in group A. Thus, bit checking is required to be effected as many as: 
     
         9×511=4599                                           . . . (i) 
    
     (2) Number of additions: 
     (a) Groups A and C: 
     As described with reference to FIG. 4, the number of additions for group A is given as follows: ##EQU2## In order to compute the sum of weights of the ten weighing machines, the addition of: 
     
         W.sub.1023 =W.sub.1 +W.sub.2 + . . . +W.sub.10 
    
     is effected, and hence 10 additions are necessary. As a result, the number of additions for groups A and C is: 
     
         2304+10=2314                                               . . . (iii) 
    
     (b) Group B: 
     The combinatorial total weight value for group B is determined by subtraction from the equation (1), and 511 computations are required. 
     (c) The number of computations required for all of groups A, B, and C is: 
     
         2314+511=2825                                              . . . (iv) 
    
     (II) Pattern 2: 
     FIG. 6 is a diagram of other combination patterns of weights which serve as a basis for the present invention. In the illustrated combination patterns, weight data items are divided into groups A and B in a manner different from the manner in which data items are divided in Pattern 1. 
     The symbol C i  used here is indicative of a set of combinations wherein selected elements have i patterns with a representing a bit number. ##EQU3## Therefore, assuming that the set A and the set B are expressed by: ##EQU4## Therefore, the set B can be derived from the set A, and combinatorial weight additions may be effected only for the combinations of the set A. 
     Thus, the number of steps required for the computations is as follows: 
     (1) Bit checking: 
     No bit checking is necessary for the set B, but only group A may be checked. Bit checking is required to be effected as many as: 
     
         10×511=5110                                          . . . (i) 
    
     (2) Number of additions: 
     (a) Groups A and C: 
     The number of additions for group A is given as follows: ##EQU5## The sum of weights of the 10 heads for group C is: 
     
         .sub.10 C.sub.10 ×10=10                              . . . (iii) 
    
     The number of additions for groups A and C is: 
     
         (ii)+(iii)=1930+10=1940                                    . . . (iv) 
    
     (b) Group B: 
     Group B is determined by subtracting the combinatorial total weight of group A from group C, the number of subtractions required is 511. 
     (c) The number of computations required for all of groups A, B, and C is: 
     
         1940+511=2451                                              . . . (v) 
    
     (III) Pattern 3: 
     FIG. 7 is a diagram of combination patterns according to an embodiment of the present invention. Pattern 3 is a mixture of the conventional patterns shown in FIG. 4 and Pattern 1 in FIG. 5. More specifically, according to the combination patterns of FIG. 7, the 1st through 8th weighing machines are in groups B, C and the 9th and 10th weighing machines are in group A, with group B being divided into group B 1  and group B 2  (which is a complement of group B 1 ). Therefore, the following relationship is present between groups B 2  and B 1  : 
     
         B.sub.2 =B.sub.1 =W.sup.8 -B.sub.1                         . . . (7) 
    
     (where W 8  is representative of the total weight of the 1st through 8th weighing machines) 
     The number of steps required in this case is as follows: 
     (1) Bit checking: 
     Bit checking is effected for the 1st through 7th weighing machines in group B 1  as many times as 
     
         7×127=889                                            . . . (i) 
    
     (2) Number of additions: 
     (a) First the number of additions for W 1  -W 127  for group B 1  is as follows: ##EQU6## 
     (b) Then, one addition is effected for W 3  (the 10th and 9th weighing machines) for group A without bit checking . . . (iii). 
     (c) 127 subtractions are effected according to the equation (7) for computing group B 2  . . . (iv). 
     (d) The number of combinations of groups B 1 , B 2  and group A (combinations of W 1  -W 254  and W 1  -W 3 ) is: 
     
         254×3=762                                            . . . (v) 
    
     (e) The number of additions for computing the total weight of the 1st through 8th weighing machines is 8 . . . (vi). By adding (a) through (e), 
     
         448+1+127+254×3+8=1346                               . . . (vii) 
    
     (IV) Pattern 4: 
     FIG. 8 is a diagram of combination patterns according to another embodiment of the present invention. The illustrated combination patterns are a mixture of Patterns 2 and 3. Pattern 4 differs from Pattern 3 in that groups B 1 , B 2  are divided by the system of Pattern 2. The number of steps required for computations in Pattern 4 is as follows: 
     (1) Bit checking: 
     Bit checking is effected for the 1st through 8th weighing machines in group B 1  as many times as 
     
         8×127=1016                                           . . . (i) 
    
     (2) Number of additions: 
     (a) First the number of additions for W 1  -W 127  for group B 1  is as follows: ##EQU7## 
     (b) Then, one addition is effected for W 3  (the 9th and 10th weighing machines) for group A . . . (iii). 
     (c) 8 additions are effected for computing the total weight of the 1st through 8th weighing machines . . . (iv). 
     (d) 127 subtractions are effected according to the equation (7) for computing group B 2  . . . (v). 
     (e) The number of combinations of groups B 1 , B 2  and group A is: 
     
         254×3=762                                            . . . (vi) 
    
     By adding (a) through (e), 
     
         372+1+8+127+254×3=1270                               . . . (vii) 
    
     The numbers of occurrences of bit checking and computations for the conventional example and Patterns 1 through 4 are given for comparison in Table 1: 
     
                       TABLE 1______________________________________  Process    Conven-   Pattern Pattern                             Pattern                                   PatternNo.      tional    1       2      3     4______________________________________Bit checking    2040      4599    5110    889  1016Computations    1790      2825    2451   1346  1270______________________________________ 
    
     As is apparent from Table 1, although the number of computations for Patterns 1 and 2 is greater than the conventional number of computations, the number of computations for Patterns 3 and 4 is smaller than the conventional number of computations. Therefore, Patterns 3 and 4 allow a shorter time interval required for finding an optimum combination of weights. The number of occurrences of bit checking is smaller for Pattern 3 than for Pattern 4. However, Pattern 4 is more advantageous since the time required for the overall computation process is shorter as the number of computations is smaller. 
     Steps of a computation process according to Pattern 4 will be described with reference to the flowchart of FIG. 10. 
     (1) The processor 104a in the combinatorial processor unit 104 computes the total weight (W 8 ) of the 1st through 8th weighing machines in a step a. 
     (2) The processor 104a computes the weight W 3  by adding the weights of the 9th and 10th weighing machines in a step b. 
     (3) The processor 104a reads an ith combination pattern (the 1st combination pattern is 00000001) out of the combination patterns of group B 1  as shown in FIG. 9 from the data memory, in a step c. 
     (4) The processor 104a computes an ith combinatorial total weight W i  in group B 1  according to the read-out combination pattern in a step d. 
     (5) The processor 104a computes a combinatorial total weight W i  (=W 8  -W i ) in group B 2 , which is a complement of the computed combinatorial total weight W i , in a step e. 
     (6) The processor 104a makes comparison and processing for the computed combinatorial total weights W i , W i  in a step f. 
     The comparison and processing will be described in more detail with respect to steps g, i, l and h, j, m. The difference α between a target weight Ws set by the weight setting unit 105 and a combinatorial total weight W is given by: 
     
         W-Ws→α 
    
     in a comparison mode (steps g, i, l). Then, whether or not a minimum deviation β stored in the data memory is greater than the difference α is determined. If |α|&lt;β, then the minimum deviation β is replaced with the difference |α|, and a combination pattern corresponding to the difference |α| is stored in the data memory in place of the optimum combination pattern stored up to now. This process is a processing mode (steps h, j, m). Since the minimum deviation has an initial value which is set as a binary number expressed by all 1s, |α|&lt;β with the first data. 
     In a step f, the processor 104a effects the foregoing comparison and processing for the combinatorial total weights W i , W i . 
     (7) The processor 104a adds, in a step k, the combinatorial total weight W i  in group B 1  and a jth combinatorial total weight W j  in group A (For a first pattern, combinatorial total weights W 1  and W 1 ) in a step k. 
     (8) The processor 104a effects the comparisons and processing as described above in (6) according to the added combinatorial total weight (W i  +W j ) to update the data of the optimum combination pattern in steps l, m. 
     (9) The steps k through n are repeated three times to add, compare, and process j=1, 2, 3 (W 1 , W 2 , W 3 ) in group A and the combinatorial total weight W 8  in group B 1 . If j&gt;3, then the processor sets j to 1 (j←1), and the program goes to a next step in a step n. 
     (10) Then, the processor 104a adds, compares, and processes the combinatorial total weight W i  in group B 2  and W 1 , W 2 , W 3  in group A three times. When the processing of the combinatorial total weight W i  is completed, the program goes to a next step, in steps o, p. 
     (11) Finally, the processor 104a determines whether the computation of all data items in groups B 1 , B 2 , and A has been completed, that is, whether i&gt;127 in a step q. 
     If i is not greater than 127, then i is incremented by +1(i←i+1), and the program goes to the step c. The steps c through q are then repeated, and if i&gt;127, all combinatorial computations are completed. 
     When the combinatorial computations are completed, an optimum combination pattern in which the combinatorial total weight is equal or closest to the target weight value is stored in the data memory 104b. If the combinatorial total weight value of the optimum combination pattern falls within an allowable preset range, then the articles are discharged from the weighing machines according to the optimum combination pattern. 
     Although certain preferred embodiments have been shown and described, it should be understood that many changes and modifications may be made therein without departing from the scope of the appended claims.