SET-UP OPTIMIZATION FOR FLEXIBLE MANUFACTURING SYSTEMS

摘要

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.