Set-up optimization for flexible manufacturing systems

• US 5,155,679 A
• Filed: 12/18/1989
• Issued: 10/13/1992
• Est. Priority Date: 12/18/1989
• Status: Expired due to Fees

• Current Assignee: Agilent Technologies, Inc.
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Jain, Shailendra E., Williams, Paul F.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): CHUNG TRANS, XUONG MY
• Application Number:
  US07/452,528
• Time in Patent Office: 1,030 Days
• Field of Search: 364/402, 364/403, 364/468, 364/478, 364/140, 364/900, 364/200
• US Class Current: 700/106
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: H05K 13/0857 Product-specific machine setup; Changeover of machines or assembly lines to new product type
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

An iterative method of sequencing jobs in a flexible manufacturing environment where such manufacturing jobs have sequence-dependent set-up times provides for solutions which approximate optimal sequencing while requiring only modest computational resources. Initially, the invention recasts a sequence of manufacturing jobs as a dynamic traveling salesman problem (TSP), in which the system must reconfigure itself and then execute each job in the same way a salesman must visit a sequence of cities, but where the distances between cities change depending upon cities already visited. The first step of the invention reduces the difficult dynamic traveling salesman problem to a static TSP, where distances between each possible job pair are fixed as a monotonic function of parts the two jobs share in common. The second step solves the resulting static traveling salesman problem, by maximizing total distance found by exploiting part commonality between jobs, to obtain a good initial solution to the job sequencing problem. The invention further improves upon the initial solution by selectively perturbing the initial sequence and calculating any changes in the number of part swaps required to reconfigure the manufacturing system. The perturbation and calculations iterate until no improvement is found. The ending sequence should be close to optimal for the job sequence and system. As a final step, a modified "keep part needed soonest" algorithm, accounting for later sequence and overall historical use of parts, optimizes the number of configuration changes for the final sequence. To assure near-optimality for the final sequence, a lower bound calculation provides a limit on how few part changes are possible for the current collection of jobs. The inventive method readily handles job sequencing problems which are difficult or impossible to solve with conventional techniques.

Claims

1. A method of controlling the operation of a machine that is capable of performing a plurality of jobs, each job requiring a plurality of parts, the method comprising:

arranging a plurality of jobs in a first sequence;

calculating a first sequence value by assigning a pair value to each pair of jobs in the first sequence, the pair value being a monotonic function of how many parts are common to both jobs of the pair, and summing the pair values of all the pairs of jobs in the first sequence;

if the monotonic function is positive, finding a maximal job sequence by repeating the arranging and calculating steps for each of a plurality of different possible job sequences and selecting that sequence which has the largest sequence value;

if the monotonic function is negative, finding a maximal job sequence by repeating the arranging and calculating steps for each of a plurality of different possible job sequences and selecting that sequence which has the smallest sequence value;

providing the parts required by the various jobs to the machine in the order of the maximal job sequence; and

causing the machine to perform the jobs with the provided parts in the order of the maximal job sequence.

2. A method as in claim 1 wherein the arranging and calculating steps comprise:

assigning a pair value to each possible pair of jobs;

arranging the jobs in the sequence; and

summing the pair values of all the pairs in the sequence to obtain the sequence value.

3. A method as in claim 1 wherein the monotonic function comprises setting the pair value equal to the number of parts common to both jobs of the pair.

4. A method as in claim 1 wherein arranging the jobs in a sequence comprises determining a sequence by evaluating a traveling salesman algorithm.

5. A method as in claim 1 wherein the monotonic function is positive and finding a maximal job sequence comprises determining an optimal configuration state for each job in the maximal job sequence.

6. A method as in claim 5 wherein determining the optimal configuration state comprises using a keep-part-needed-soonest algorithm.

7. A method as in claim 5 and further comprising:

generating a first solution set of job sequences by deriving a plurality of variant sequences from the maximal job sequence by a predetermined perturbation algorithm;

determining an optimal configuration state for each job in each variant sequence;

defining a swapping value for each sequence in the first solution set by summing the part swaps for each successive pair of optimal configuration states of the sequence; and

determining a second solution job sequence by selecting, from among the job sequences in the first set, that sequence having the lowest swapping value.

8. A method as in claim 7 and further comprising:

comparing an n-th solution sequence with an (n-1)-th solution sequence;

if the sequences have the same swapping value, selecting the n-th solution sequence as an optimal solution sequence; and

if the sequences do not have the same swapping value;

generating an n-th solution set of job sequences by deriving a plurality of variant sequences from the n-th solution sequence by a determined perturbation algorithm;

determining an optimal configuration state for each job in each variant sequence of the n-th solution set;

defining a swapping value for each sequence in the n-th solution set by summing the part swaps for each successive pair of optimal configuration states of the sequence; and

determining an (n+1)-th solution job sequence by selecting, from among the job sequences in the n-th set, that sequence having the lowest swapping value.

9. A method as in claim 8 wherein the step of determining an optimal configuration state for each job in each variant sequence of the n-th solution set comprises using a keep-part-needed-soonest algorithm.

10. A method as in claim 9 and further comprising determining an optimal configuration state for each job of the optimal solution sequence by using a modified keep-part-needed-soonest algorithm, the modified algorithm comprising assigning priorities for removing from a current configuration state any parts not required for any pending job of the sequence.