Structured Partitioning Problems

S. Anily and A. Federgruen
Additional contact information
S. Anily: University of British Columbia, Vancouver, Canada, and Tel Aviv University, Tel Aviv, Israel
A. Federgruen: Columbia University, New York, New York

Operations Research, 1991, vol. 39, issue 1, 130-149

Abstract: In many important combinatorial optimization problems, such as bin packing, allocating customer classes to queueing facilities, vehicle routing, multi-item inventory replenishment and combined routing/inventory control, an optimal partition into groups needs to be determined for a finite collection of objects; each is characterized by a single attribute. The cost is often separable in the groups and the group cost often depends on the cardinality and some aggregate measure of the attributes, such as the sum or the maximum element. An upper bound ( capacity ) may be specified for the cardinality of each group and the number of groups in the partition may either be fixed or variable. The objects are indexed in nondecreasing order of their attribute values and within a given partition the groups are indexed in nondecreasing order of their cardinalities. We identify easily verifiable analytical properties of the group cost function under which it is shown that an optimal partition exists of one of three increasingly special structures, thus allowing for increasingly simple solution methods. We give examples of all the above listed types of planning problems, and apply our results for the identification of efficient solution methods (wherever possible).

Keywords: queues: structured set partitioning problems; algorithms (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.1.130 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:1:p:130-149

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().