Skip to main content
SpringerLink
Log in

Matching problems in selective assembly operations

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We consider several different matching problems that are motivated by applications to selective assembly operations. In the case of maximum cardinality problems, we provide linear time greedy algorithms which we prove optimal via a min-max theorem. We also consider a weighted version and provide a polynomial time algorithm to find the optimal solution.

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

  1. R.W. Bolz, Production Processes, 5th ed., Conquest Publications, Winston-Salem, 1977.

    Google Scholar 

  2. F. Glover, Maximum matching in a convex bipartite graph, Naval Research Logistics Quarterly 14(1967)313 - 316.

    Google Scholar 

  3. P. Hall, On representations of subsets, Journal of the London Mathematical Society 10(1935)26 -30.

    Google Scholar 

  4. T. Iyama, M. Mizuno, S. Goto and T. Koga, A race matching method for ball bearing manufacture, Working Paper, Department of Mechanical Engineering, Iwate University, 4-3-5 Ueda, Morioka 020, Japan, 1994.

    Google Scholar 

  5. R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85 - 103.

    Google Scholar 

  6. H.W. Kuhn, The Hungarian method for solving assignment problems, Naval Research Logistics Quarterly 2(1955)83 - 97.

    Google Scholar 

  7. H.L. Lee, W.H. Hausman and G.J. Gutierrez, Optimal machine settings of imperfect component production processes for assembly operations, IEEE Transactions on Robotics and Automation 6(1990)652 - 658.

    Google Scholar 

  8. L. Lovász and M.D. Plummer, Matching Theory, Akademiai Kiadó, Budapest and North-Holland, Amsterdam, 1986.

    Google Scholar 

  9. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley-Interscience, New York, 1988.

    Google Scholar 

  10. K.C. So and C.H. Scott, Optimal production sequence for a product with matching components, Working Paper, Graduate School of Management, University of California, Irvine, 1993.

    Google Scholar 

Download references

Authors
  1. C.R. Coullard
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A.B. Gamble
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. P.C. Jones
    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

Coullard, C., Gamble, A. & Jones, P. Matching problems in selective assembly operations. Annals of Operations Research 76, 95–107 (1998). https://doi.org/10.1023/A:1018960924601

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018960924601

Keywords

Search

Navigation