Abstract:
A method of scheduling the building sequence of a plurality of objects on an assembly line in order to minimze the cost of building the objects is disclosed. Each object has a plurality of attributes, which together with the position of the object in the sequence, affects the overall cost of the build sequence. A computer is provided with a representation of the object, its attributes, and a procedure for calculating the cost associated with any arrangement of the attributes. An initial build sequence is generated using the representation which has a minimal cost associated with the arrangement of at least one of the attributes. A final build sequence is generated in accordance with a simulated annealing algorithm which utilizes a scoring function that includes the costs defined by the procedure, those costs associated with the attributes being independently weighted in accordance with a temperature varying function. A representation of the final build sequence usable for construction of the object is then provided.

Description:
This is a continuation of application Ser. No. 199,696 filed on May 27, 1988 now abandoned. 
    
    
     FIELD OF THE INVENTION 
     This invention relates to methods of optimizing the arrangement of objects to decrease the cost of production, and more particularly to a vehicle build sequence optimization method utilizing an improved simulated annealing technique. 
     BACKGROUND OF THE INVENTION 
     The order in which vehicles or other products are built on an assembly line greatly influence the total production cost of the product. There are costs that favor grouping certain options and those that favor spacing others. For example, paint color is an option that will tend to group cars. There is a cost associated with painting consecutive cars different colors that is derived from purging the sprayer nozzle of paint. Another possible cost is the decrease in quality that occurs when colors are changed, due to paint in the air settling on the wrong car. Assuming all cars are of high quality after leaving the paint operation, this would then imply a cost to repaint the car. Two adjacent cars will have a paint cost that is lower if they have the same color than if they have different colors. The cost is however non-symmetric: That is, a white car followed by a black car would have a lower cost than a black car followed by a white car, since it is easier to purge white paint with black paint than vice-versa. 
     With respect to spacing considerations, an eight-cylinder engine is a good example of an attribute that will suggest that certain cars be spaced far apart during assembly. It takes more time to install an eight-cylinder engine that it does to install a four-or-six-cylinder engine. Thus, it is desirable to leave the maximal space between occurrences of this option. If ten percent of orders have eight-cylinder engines, the best one can do is to space the ones containing these engines every ten cars. Spacing some farther than this will cause others to be spaced closer. If the option is spaced closer than the average, then workers may be rushed. If they are spaced farther apart than the average, there may be idle capacity. Hence there is a cost that is minimum at the average spacing and increases when any spacing deviates from this. The tighter the distribution of spacings cluster around the average, the lower the total cost will be. 
     Simulated annealing is a randomized local search method for finding near optimum solutions to combinatorial optimization problems and has been discussed extensively in the literature. See for example Optimization by Simulated Annealing by S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science Volume 220, Page 671-680. The method is particularly applicable to problems where the number of possible solutions is extremely large and there is no efficient way to examine each possible solution. In U.S. Pat. No. 4,495,559 simulated annealing is applied to the problem of integrated circuit placement and layout. 
     Simulated annealing finds a minimum of an objective function ##EQU1## 
     where the symbol x represents the set of variables which completely specify the configuration of the objects which compose the combinatorial problem. Each term (labeled by i), called an objective, in Eq. 1 is associated with some attribute of the configuration and is designed to decrease when the configuration possesses a desired arrangement of that attribute. 
     Simulated annealing searches out a minimum of Eq. 1 by making a series of successive changes from some starting configuration. Let DELTA x be such a change and DELTA 0=0(x +DELTA x)-0(x) the corresponding change in 0(x). If DELTA 0 is negative, simulated annealing accepts the changed configuration. If DELTA 0 is positive, simulated annealing accepts the changed configuration with probability 
     
         P=exp (-DELTA 0/T),                                        (2) 
    
     where T is a parameter, called the temperature, which changes during the course of the simulated annealing run according to an annealing schedule. A possible schedule is shown in FIG. 1. Essential properties of an annealing schedule are that the temperature be &#34;high&#34; for some period at the beginning of the schedule and decrease to a &#34;low&#34; value at the end. During the high part of the schedule, simulated annealing accepts many unfavorable changes and thus explores many configurations. As the temperature decreases the method is designed to settle into a minimum of 0(x). If the run is long enough and the cooling slow enough, it can be proved that simulated annealing will find the absolute minimum of 0(x). 
     The difficulty with simulated annealing is that with some problems so much computer time is required that the method is not practical for such problems. Run time can be unacceptably long when some of the desired configurations conflict with one another, i.e., when a change which decreases one of the terms of Eq. 1 almost always increases another. 
     BRIEF DESCRIPTION OF THE INVENTION 
     The present invention is particularly useful when the following conditions exist: 
     1. One or more of the objectives making up the objective function, hereinafter referred to as &#34;special&#34; objectives, can be mimimized using some constructive algorithm or recipe. 
     2. A configuration that is near optimum for these special objectives in conjunction with an near optimum for the remaining objectives is found only after an unacceptable amount of computer time by the random process of simulated annealing. 
     3. A configuration, such as given in (2) will be altered with high probability by the random process of simulated annealing. 
     In accordance with the present invention a constructive algorithm is used to select a configuration which minimizes the special objectives that satisfy the three conditions mentioned above. If there is more than one special objective, it must be true that the objectives do not conflict strongly. This initial step is designated the preplacement step. Starting from this initial configuration, simulated annealing is used with a new temperature dependent objective function, ##EQU2## In Eq. 3, the first sum is over the terms corresponding to the objectives satisfied by the preplacement (i), and the second sum is over the remainder (j). F i  (T) is varied with T so that it initially starts at a value high enough to prevent changes in the corresponding (i) objective functions and ends at a value of 1. The value of F i  should remain large while the objectives j are optimized. After the value of the objective functions j have plateaued, F i  (T) can be dropped to the final value of 1. Varying F i  (T) in this manner retains the advantageous information given in the preplacement step for objectives i while optimization progresses over objectives j and allowing further optimization of the objectives i. 
     The method of the present invention is faster than standard simulated annealing since: Condition (2) holds, and thus much time would be spent finding the optimum configuration, while condition (1) provides a quick way of finding it; and Eq. 3 is used to defeat the drawback of condition (3). 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more complete understanding of the invention may be had from the following detailed description of the invention which should be read in conjunction with the drawing in which: 
     FIG. 1 is an example of an annealing schedule, i.e. the variation of T with the number of attempted changes. 
     FIGS. 2a and 2b are examples of a variation of the temperature scaling of the objective function. FIG. 2.1 plots this variation with T, while FIG. 2.2 plots this variation with the number of attempted changes. 
     FIGS. 3a, 3b, 3c and 3d are four configuration designed to show the usefulness of the application of the invention to a particular scheduling problem. 
     FIG. 4 shows the progress of the optimization with and without the application of the invention. 
     FIG. 5 is a block flowchart of a sequencing optimization. 
     FIGS. 6 through 14 are individual elements of the flow chart. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A simple example will demonstrate the power of the method of the present invention. Assume an object such as a vehicle with two attributes, color and size or another attribute which affects the complexity of the build of the vehicle. Assume that these vehicles are built in a sequential fashion on an assembly line. The only two colors are white and black, and the only two sizes are big and small. In order to build these objects cheaply, it is desirable to build all objects of the same color together in order to reduce the amount of paint used. An optimum configuration for the color objective would thus be all white objects followed by all black objects as shown in FIG. 3a. Big objects take more time to build then little ones so it is desirable to space the big objects apart from each other to reduce manpower requirements and improve quality. In addition, they must be at least one unit apart. An optimum configuration for the size objective is shown in FIG. 3b. The complication occurs when both objectives are desired simultaneously, and all the big cars are black; then it is difficult to both group and space together. If the penalty for switching colors is less than the penalty for spacing the large objects with one small one between, then the optimum configuration would be FIG. 3c. The difficulty is how to arrive at this configuration in an efficient manner. 
     In the standard simulated annealing method, the most likely final configurations look like FIG. 3d. That is, there are many big, black objects in the white area. The big objects must be spaced out very well in the black area to allow room for all of them. It is very difficult using simulated annealing, due to its random nature, to progress from FIG. 3d to FIG. 3c. 
     Conditions (1-3) mentioned above are met for this application of the invention: 
     (1) The attribute to preplace is color; a simple constructive algorithm will place the white objects together and the black objects together. 
     (2) The optimum configuration (FIG. 3c) is not very likely to be found at random, since it requires a long-range structure in both the size and color attribute. This is not to say that it won&#39;t be found; it is merely unlikely or will require an unacceptably large amount of computer time. 
     (3) Given a configuration close to this optimum configuration, the standard simulated annealing method will move quickly away from the optimum by moving the big objects into the white area rather than spacing them out in the black area. Such moves are always accepted since they result in a decrease in the total objective function. 
     In general the steps of the invention are to first, assign the attribute COLOR to set i for preplacement and assign the attribute SIZE to set j for later consideration. Second, produce an initial configuration by placing all white objects ahead of the black objects. Third, construct an appropriate F i  (T) to prevent the color preplacement from being destroyed until most of the size objective has been satisfied. The square function in FIG. 2a shows a good example of the F i  (T) for this case. Fourth, simulated annealing is performed with the objective function in Eq. 3. This will force the configuration to space out the big objects in the black region first; when the drop in F i  (T) occurs, most (if not all) of the size objective will be satisfied and the color objective will only be slightly degraded, ending up in the configuration given in FIG. 3c. 
     By observing the objective function, the point at which F i  (T) should drop from a large to a small value may be determined. The usual progress of the minimization of the actual (F i  (T)=1) objective function schematically follows the curve shown in FIG. 4. While the actual objective function drops, F i  (T) is kept large. When it plateaus (Point X in FIG. 4) F i  (T) is dropped to 1. Curve A is the one the actual objective function follows for the standard method. Curve B is the one followed If F i  (T) is kept large. Curve C is the one followed when F i  (T) is dropped to 1.; the crossover from curve B to C occurs at point X. If X is too early (X 1 ), then curve D is followed. This is inefficient; curve D turns into curve A if X is early enough. If X is too late, then curve E is followed. This is also inefficient, since time was spent not doing anything constructive from X to X 2 . One may thus pick X by using these observations. X may be picked automatically, but for similar sets of constraints X is usually the same value within a few percent, so it may be fixed for successive runs on similar problems without incurring inefficiency. 
     The total amount of computer resources used in the present invention is far less than that used in standard simulated annealing, which will remain in configurations similar to FIG. 3.4 for almost all of the computer run. 
     As previously indicated, the invention is particularly useful in the optimization of the sequence in which objects are assembled on an assembly line. For example, the objects may be vehicles or any of the various sub-assemblies that comprise a vehicle, such as an engine. 
     This optimization in accordance with the invention provides an objective function comprising two parts. The two parts compete with each other in that a configuration optimal for one is not optimal for the other. The two parts of the objective function are first, color, where it is desirable to minimize the number of switches from a color to a different color as the objects progress down the assembly line; and second, size, where it is desirable to maximize the time, or distance, between two objects with a large size attribute. In order to be in conflict, near spacings of objects with the size objective must entail a larger penalty than a color change, and far spacings of objects with the size objective must entail a smaller penalty than a color change; in addition, the objects must have a larger percentage of the large size attribute in one or the other color. 
     In accordance with the invention the optimization further provides a quick constructive method of attaining one of the objectives. In the example this involves placing those objects with one color first, another color second, and so on. This initial configuration is such that it will be altered with a probability nearly one by the random actions of swapping objects, central to the simulated annealing process, since a move that separates two objects of large size attribute that are close to each other will result in a decrease in the objective function, despite the addition of a penalty due to changing the color. This results from the fact that a decrease in the objective function is always accepted by simulated annealing. 
     The optimization method of the present invention further provides a method of varying the weights of the part of the objective function corresponding to the attribute that was preplaced. The weighting factor is varied via the function F(T)=1+A/(1+exp ((Tmid-T)/scale)) where A is set to a number larger than ten times the largest term in the objective function; and Tmid is set to a number determined via several trials to minimize the CPU time required for a sample problem, as described above in connection with FIG. 4. Scale is set to a sufficiently small value that the transition in F from 1+A to 1 occurs in a narrow range; setting scale to 10 -20  is usually sufficient, but other values of scale will possibly better or worse efficiency; trial and error, as in the case of Tmid, will determine the best value. 
     The criteria for the application of the simulated annealing algorithm is satisfied by introducing: first, a method of defining a sequence, by giving a list of positions in which to build the objects; second, a method of scoring the configuration, by using the objective functions mentioned above; third, generating new configurations, by swapping pairs of objects; fourth, providing a means of accepting the new configuration, by using the well-known exponential acceptance criterion; fifth, varying the acceptance criterion in an incremental fashion by using the well-known method of changing the temperature parameter T in an exponential fashion. 
     A more detailed understanding of a preferred embodiment of the invention may be had with reference to the flow chart of FIGS. 5-14 and the FORTRAN Program of APPENDIX A. 
     Referring initially to FIG. 5, which depicts the overall process which involves first, as indicated in block 1, gathering the data describing the current system, second, as indicated in block 2, preplacing the objects in order to minimize the color attribute, as set forth in the quick constructive method; third, as indicated in block 3, performing an optimization run using the well-known method of simulated annealing except that the scoring function weights the preplaced attribute with the temperature-varying function F as given above, and fourth, as indicated in block 4, outputting the final configuration to a form usable subsequently. 
     Referring next to FIG. 6, a detailed description of block 1 of FIG. 5 is provided. There are three general steps in the input of data labeled 5 through 7. The first step labeled 5 involves the reading in of the objective functions from a file. These objective functions will be used in calculating the scoring that determines the improvement of the sequence. 
     In step 6, the second step, the descriptions of the objects or vehicles are read in from a file. These descriptions include a unique identifier for each object, the color of the object, and the size attribute of the object. The unique identifier will be used to assign the object to a specific position in the sequence. The two attributes, color and size, will be used to calculate the value of the objective function for a given sequence. 
     In step 7, the third step, parameters defining the annealing schedule and the parameters defining the variation of F with the annealing schedule are read in from a file. The annealing schedule defines the variation of the parameter T with the progress of the program; T is used to decide the conditional acceptance of a change in accordance with the well-know simulated annealing expression. The parameters defining F determine the variation of F with the parameter T. 
     Referring next to FIG. 7, a detailed description of block 2 of FIG. 5 is provided. A functional flow chart of the preplacement step is provided in blocks 8 through 16. From a functional standpoint, the objects are examined in turn for the first color, and placed; then the next color, and placed; and so on, until all objects are placed in an initial configuration. 
     In FIG. 7 from a serial standpoint the following occurs: The first step 8 is to start the placement at the first position in the sequence, with the first color. Next in step 9 the first object in the set of vehicle descriptions is examined. In step 10, a decision is made as to whether the current object is of the current color; the first time through, the current color is the first color and the current object is the first object, but in subsequent returns from steps 13 or 15 the current object and current color may be changed. If the current object has the current color as an attribute, then step 11 is executed. This places the current object in the current position, and increments the current position so that the next object to be placed will be at the next position. Next, a test is made in step 12 to see if all objects have been examined for the current color. If not, then the next object is made the current object, and the process transfers back to step 10. If all objects have been examined, then a test is made in step 14 to see whether all positions have been placed. If not, then the next color is made the current color to be placed in step 15, and the process continues at step 9. If all objects have been placed, then process continues to step 16 which signals the end of the preplacement process. At this point block 2 of FIG. 5 has been completed, and an initial configuration has been established by the constructive method just defined. 
     Referring next to FIG. 8, a detailed description of block 3 of FIG. 5 is provided. A functional flow chart of the optimization step is provided in blocks 17 through 26. From a functional standpoint simulated annealing is performed in accordance with the well-known method except that the parameter F is varied in accordance with the  invention and used in the calculation of the objective function, or cost, when an evaluation of the scoring function is required by the well-known method. 
     In FIG. 8 from a serial standpoint, the current value of parameter T is set in step 17 to the initial value of the annealing schedule as determined in step 7 of FIG. 6. Next is step 18 the value of F for the current value of T is determined using the parameters determined in step 7 of FIG. 6. The current cost of the current configuration is determined in step 19. In step 20, the current object at which swaps will be attempted is started at the first object. In step 21, the current object is swapped with another, random, one. In step 22, the cost of the new configuration is determined. The swap undergoes the well-know acceptance procedure in step 23. In step 24 a test is made to see if an attempt has been made to swap all objects. If all objects have not been swapped, the current object to swap is updated to the next one and the process continues at step 21. If an attempt has been made to swap all the objects in the sequence, then a test has been made in test 25 to see if the annealing schedule has been completed. If not, the value of the parameter T is updated and the process continues at step 18. If the annealing schedule has been completed, then the process continues to step 26 which signals the end of the optimization process. At this point block 3 of FIG. 5 has been completed and the configuration is at an optimum. 
     FIG. 9 is a detailed description of the procedure whereby a cost or score is generated in steps 19 or 22 of FIG. 8. From a functional standpoint, the various parts of the cost of objective function are computed, and then are added together with the weight specified by the factor F as determined by the invention. 
     From a serial standpoint, in step 27 the cost due the first part of the objective function due to the attribute preplaced in FIG. 7, the color, is determined. In step 28, the cost due to the rest of the objective function, the spacing cost, is determined. In step 29 the Value of the color cost, weighted by the current value of the parameter F, as determined in step 18 of FIG. 8, is added to the spacing cost to arrive at the final cost. Step 30 signals the end of the cost computation for the current configuration, and the steps labeled 19 or 22 of FIG. 8 are now completed. 
     FIG. 10 is a detailed description of the procedure whereby the cost due to the color attribute is determined in step 27 of FIG. 9. From a functional standpoint, the number of times the color attribute changes as one progresses along the sequence is determined, and this number is weighted by the cost for a single color switch, to arrive at the value for the color cost. 
     From a serial standpoint, in step 31 the current object is set to the first object in the sequence, and the counter that will sum the number of color switches is set to zero. In step 32 a test is made to see if there is a color change from the current object to the next object. If the test is true, the counter is incremented by one in step 33, and the process continues at step 34. If the test is false, then the process is continued at step 34. In step 34, the current object is updated to the next object in the sequence as specified in the current configuration being scored. In step 35, a test is made to see if all objects have been looked at to see of a color switch occurred. If not, then the process continues at step 21. If all objects have been looked at, the process continues at step 36. In step 36 the color cost is set to the value of the counter weighted by the value of a single color switch as determined in step 5 of FIG. 6. Step 37 signals the end of the color cost computation. 
     FIG. 11 is a detailed description of the procedure whereby the cost due to the spacing attribute is determined in step 28 of FIG. 9. From a functional standpoint, the distance between successive occurrences of each spacing objective as one progresses along the sequence is determined, and this distance is used of find a cost from a table of cost versus spacing. This cost is summed to find the total spacing cost. 
     From a serial standpoint, in step 38 the accumulator that will sum the individual contributions to the spacing cost is set to zero. In step 39 the first spacing attribute is made current; the cost due to the current spacing attribute is found in alter steps before proceeding to other spacing attributes. In step 40 the first object with the current spacing attribute is made the current object, and in step 41 the next object, where next means progressing down the sequence determined by the current configuration, is found. In step 42 the distance between the current object and the next object is used to determine the contribution to the spacing cost by examining the lookup table as determined in step 5 of FIG. 6. In step 43 a test is made to determine if all objects have been examined for the current spacing attribute. If not, then the next object, as determined in step 41, is made the current object and the process continues at step 44. If all objects have been examined, then a test is made in step 45 to see if all spacing objectives have been examined. If not, then the next spacing objective is made current in step 46 and the process continues at step 140. If all spacing objectives have been examined, then step 47 signals the end of the spacing cost computation. 
     FIG. 12 is a detailed description of the procedure whereby a trial configuration is generated in the swap procedure of step 21 in FIG. 8. From a functional standpoint, a object different from the current object is determined and the positions occupied in the configuration are interchanged. 
     From a serial standpoint, in step 48 an object is picked at random from the list of objects determined in step 6 of FIG. 6. A test is made in step 49 to see if the random object is the current object. If it yes, then the process continues at step 48, to once again pick a random object. If the random object is different, then the sequence positions of the current object and the random object as defined by the current configuration are interchanged, and step 51 signals the end of the swap procedure. 
     FIG. 13 is a detailed description of the procedure whereby the trail swap generated in step 22 of FIG. 8 is accepted as defining the current configuration in step 23 of FIG. 8. This acceptance procedure follows the well-known method of simulated annealing. From a functional standpoint, the swap is accepted according to the probability determined by the ratio of the change in the temperature-dependent objective function of this invention to the current value of the temperature parameter. 
     From a serial standpoint, in step 52 a random number r is generated with a value between zero and one and in step 53 there is a computation of the value of R equal to the exponential to the base e of the current value of the temperature-dependent objective function minus the new value of the temperature-dependent objective function, divided by the current value of T, the temperature. The computed value of R is then compared with the value of r from step 52 in step 53 and if R is greater than r, the interchange will be accepted in step 55. The current cost is then set to the value of the new cost in step 56 and the process continues at step 59, signaling the end of the acceptance routine. If the comparison in step 54 shows the value of R is less than the value of r then the interchange is rejected in step 57 and in step 58 the sequence positions are reestablished as they were prior to the interchange determined in the swap step 21 of FIG. 8. The process then continues in step 59, signaling the end of the acceptance routine. 
     Referring next to FIG. 14, a detailed description of block 4 of FIG. 5 is provided. A functional flow chart of the output step is provided in blocks 60 through 61. From a functional point of view, the final configuration of the optimization procedure is placed in a form usable for actual building of the objects. from a serial standpoint, in step 60 the optimal configuration is placed in a computer file, and the process continues at step 61, which signals the end of the output routine. 
     The illustrations of FIGS. 5 through 14 may be assembled into a single programming implementation as set forth in Appendix A. The program is written in the FORTRAN language well-known in the art and is within the capabilities of most computers. The particular implementation of is compatible with the SUN Microsystems computers. ##SPC1##