Skip to main content
SpringerLink
Log in

Design of a real-time AND/OR assembly scheduler on an optimization neural network

  • Papers
  • Published:
Journal of Intelligent Manufacturing Aims and scope Submit manuscript

Abstract

The problem of finding an AND/OR precedence-constraint assembly schedule using optimization neural computation is presented. The precedence relationships of assembly operation result from the geometric constraints of subtasks. Because of the existence of geometric constraints among assembly subtasks, the assembly operation involves AND/OR precedence relationships; that is, the order of assembly crucially determines whether the desired task can be achieved. A feasible assembly schedule is a schedule that satisfies these AND/OR precedence constraints.

It has been shown that all the feasible assembly schedules can be generated by transforming geometric constraints of subtasks to the pattern-matching operation. Using the question-answer pattern and pattern-matching operation, the assembly scheduling problem can be transformed into an AND/OR precedence-constrained traveling salesman problem (TSP). Two precedence-constrained TSPs, cost-constrained TSP (CCTSP) and state-constrained TSP (SCTSP), are discussed. The CCTSP artificially sets the cost of the prohibited moves to a very large value which ensures that the constraints are satisfied, while the SCTSP restricts the movement of next assembly subtasks. The advantage of the SCTSP over CCTSP in the generation of the assembly schedule will be illustrated.

A novel method proposed here is to obtain the best AND/OR precedence-constraint assembly schedule using neural network computation. The geometric constraints of an assembled object are transformed into the elements of the connection matrix which specifies the connection strength among neurons. A modified Hopfield network is used to tackle the AND/OR precedence-constraints assembly scheduling problem. Multirobot assembly sequences generation is also discussed. The designed algorithm can accommodate various constraints and applications. Detailed algorithms, examples and experiments are presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aiyer, S. V. B., Niranjan, M. and Fallside, F. (1990) A theoretical investigation into the performance of the Hopfield model.IEEE Transactions on Neural Networks,1 (2), 204–215.

    Google Scholar 

  • Bellmore, M. and Hong, S. (1974) Transformation of multisalesmen problem to the standard traveling salesman problem.Journal of ACM,21 (3), 500–504.

    Google Scholar 

  • Chang, K. H. and Wee, W. G. (1988) A knowledge-based planning system for mechanical assembly using robots.IEEE Expert Magazine, 18–30.

  • Chen, C. L. P. (1990) Neural computation for planning AND/OR precedence-constraint robot assembly sequences, inProceedings of International Joint Conference on Neural Networks,I, pp. 127–142.

  • Chen, C. L. P. (1991) Automatic generation assembly sequences by pattern-matching,IEEE Transactions on Systems, Man and Cybernetics,SMC-21 (2) pp. 376–389.

    Google Scholar 

  • De Fazio, T. L. and Whitney, D. E. (1987) Simplified generation of all mechanical assembly sequences.IEEE Journal of Robotics and Automation,RA-3 (6), 640–658.

    Google Scholar 

  • Fox, B. R. and Kemp, K. G. (1987) Reasoning about opportunistic schedules, inProceedings of 1987 IEEE International Conference of Robotics and Automation, pp. 1876–1882.

  • Homem de Mello, L. S. and Sanderson, A. C. (1986) AND/OR graph representation of assembly plans, inProceedings of AAAI Conference, pp. 1113–1119.

  • Hopfield, J. J. (1982) Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Science,79, 2554–2558.

    Google Scholar 

  • Hopfield, J. J. and Tank, D. W. (1985) Neural computation of decisions in optimization problems.Biological Cybernetics,52, 141–152.

    Google Scholar 

  • Kahng, A. (1989) Traveling salesman heuristics and embedding dimension in the Hopfield model, inProceedings of 1989 International Joint Conference on Neural Networks,I, pp. 513–520.

  • Tagliarini, G. A. and Page, E. W. (1987) Solving constraint satisfaction problems with neural networks, inProceedings of 1987 International Conference on Neural Networks,III, pp. 741–747.

  • Takeda, M. and Goodman, J. W. (1986) Neural network for computation: number representation and programming complexity.Applied Optics,25 (18), 3033–3046.

    Google Scholar 

  • Van den Bout, D. E. and Miller, T. K. (1988) A traveling salesman objective function that works, inProceedings of 1988 International Conference on Neural Networks,III, pp. 299–303.

  • Wacholder, E., Han, J. and Mann, R. C. (1989) A neural network algorithm for the multiple traveling salesmen problem.Biological Cybernetics,61 (1), 11–19.

    Google Scholar 

  • Wilson, G. V. and Pawley, G. S. (1988) On the stability of the traveling salesman problem algorithm of Hopfield and Tank,Biological Cybernetics,58, 63–70.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Wright State University, 45435, Dayton, OH, USA

    C. L. Philip Chen

Authors
  1. C. L. Philip Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Philip Chen, C.L. Design of a real-time AND/OR assembly scheduler on an optimization neural network. J Intell Manuf 3, 251–261 (1992). https://doi.org/10.1007/BF01473902

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01473902

Keywords

Search

Navigation