Skip to main content
SpringerLink
Log in

A variation of the generalized assignment problem arising in the New Zealand dairy industry

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

Abstract

Within the New Zealand dairy industry, milk is collected from farms by road tanker vehicles and delivered to the factories of a dairy company for processing. Before the tankers can be scheduled to pick up the milk, each company must decide to which factory the output of each of its client farms is to be sent. We present a mathematical model of this allocation problem and solution procedures for it. The model is a variation on the generalized assignment problem. The problem is NP-hard, which reinforces the search for efficient heuristics for it. We present heuristics which yield solutions close to optimality in a reasonable amount of computing time for problems of the size commonly encountered in the dairy industry.

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.

Similar content being viewed by others

References

  1. M.M. Amini and M. Racer, A rigorous computational comparison of alternative solution methods for the generalized assignment problem, Management Science 40(1994)868–890.

    Google Scholar 

  2. M.L. Fisher and R. Jaikumar, A generalized assignment heuristic for vehicle routing, Networks 11 (1981)109–124.

    Google Scholar 

  3. L.R. Foulds, An information system for milk tanker scheduling, Proceedings 28th Annual Conference of the Operational Research Society of New Zealand, University of Canterbury, Christchurch, New Zealand, August 1992, pp. 199–206.

    Google Scholar 

  4. A.M. Frieze and M.R.B. Clarke, Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses, European Journal of Operational Research 15 (1984)100–109.

    Google Scholar 

  5. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1978.

    Google Scholar 

  6. S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Codes, Wiley, New York, 1990.

    Google Scholar 

  7. G.T. Ross and R.M. Soland, A branch and bound approach for the generalized assignment problem, Mathematical Programming 8(1975)91–105.

    Google Scholar 

  8. Sciconic/VM, EDS-Scicon, Milton Keynes, England.

Download references

Authors
  1. L.R. Foulds
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J.M. Wilson
    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

Foulds, L., Wilson, J. A variation of the generalized assignment problem arising in the New Zealand dairy industry. Annals of Operations Research 69, 105–114 (1997). https://doi.org/10.1023/A:1018968625626

Download citation

  • Issue Date:

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

Keywords

Search

Navigation