×

On the selection and assignment with minimum quantity commitments. (English) Zbl 1091.90529

Chwa, Kyung-Yong (ed.) et al., Computing and combinatorics. 10th annual international conference, COCOON 2004, Jeju Island, Korea, August 17–20, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22856-X/pbk). Lecture Notes in Computer Science 3106, 102-111 (2004).
Summary: Traditional selection and assignment problems analyze how to select and assign the suppliers to meet demands within minimum total costs. The maximum capacity and the fixed selection costs are two major restrictions imposed on suppliers, and extensively studied in literature.
In practice, another constraint, named as Minimum Quantity Commitment (MQC), needs to be satisfied by each selected supplier. It is stipulated for the global transportation by the US Federal Maritime Commission. According to the MQC, when assigning containers for shipments to US, the international companies, including the Royal Philips Electronics Company, must insure each selected shipping agent to have a certain minimum quantity of containers. This increases difficulties for them to seek the optimal schedule with minimum total costs. The MQC constraint has been seldom studied before, which motivates us to present its hardness results for the selection and assignment problems.
For the entire collection see [Zbl 1053.68004].

MSC:

90B80 Discrete location and assignment
90C60 Abstract computational complexity for mathematical programming problems
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI