Boots – shoes – and leggings
Patent
1989-12-18
1992-10-13
Envall, Jr., Roy N.
Boots, shoes, and leggings
364468, 364478, G05F 1520, G05F 1546
Patent
active
051556790
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.
REFERENCES:
patent: 4835687 (1989-05-01), Martin
patent: 4852001 (1989-07-01), Tsushima et al.
patent: 4866628 (1989-09-01), Natarajan
patent: 4887218 (1989-12-01), Natarajan
patent: 4896269 (1990-01-01), Tong
patent: 4956784 (1990-09-01), Hadavi et al.
"Solution of a large-scale traveling salesman problem" by G. Dantzig, R. Fulkerson, and S. Johnson; The Rand Corporation, Santa Monica, Calif. (Journal of the Operations Research Society of America, vol. 2, 1954).
B. Golden et al. "Approximate Traveling Salesman Algorithms" Operations Research, vol. 28, No. 3, Part II, May-Jun. 1980, pp. 694-711.
Jonathan F. Bard et al. "A Heuristic for Minimizing the Number of Tool Switches on a Flexible Machine" IIE Transactions, vol. 20, No. 4, Dec. 1988, pp. 382-391.
S. Lin and B. W. Kernighan, "An Effective Heuristic Algorithm for the Traveling Salesman Problem", Bell Telephone Laboratories, Oct. 15, 1971.
Ichiro Inoue and Masao Managaki, "PROPS: an Interactive Simulator for Job Shop Production System Evaluation" N.E.C. Research & Development, No. 71, Oct. 1983, pp. 89-96.
Christopher S. Tang, "A Job Scheduling Model for a Flexible Manufacturing Machine" Proceedings of 1986 IEEE Conference on Robotics and Automation, pp. 152-155.
C. F. Lofgren and L. F. McGinnis, "Dynamic Scheduling for Flexible Printed Circuit Card Assembly" pp. 1294-1297.
Shahrukh Adi Irani et al. "Single Machine Setup-dependent Sequencing Using a Setup Complexity Ranking Scheme" Journal of Manufacturing Systems, vol. 7(1988) No. 1, pp. 11-23.
Christopher S. Tang et al. "Models Arising from a Flexible Manufacturing Machine, Part 1: Minimization of the Number of Tool Switches" Operations Reserach, vol. 36, No. 5, Sep.-Oct. 1988, pp. 767-777.
Jain Shailendra E.
Williams Paul F.
Chung Xuong M.
Envall Jr. Roy N.
Hewlett--Packard Company
LandOfFree
Set-up optimization for flexible manufacturing systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Set-up optimization for flexible manufacturing systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set-up optimization for flexible manufacturing systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1306077