This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Arbib, C. Articles by Marinelli, F. Search for Related Content

Exact and Asymptotically Exact Solutions for a Class of Assortment Problems

Università degli Studi di L'Aquila, Dipartimento di Informatica, Coppito, I-67010 L'Aquila, Italy
Università Politecnica delle Marche, Dipartimento di Ingegneria Informatica, Gestionale e dell'Automazione, I-60131 Ancona, Italy
arbib{at}di.univaq.it
marinelli{at}diiga.univpm.it

Mass customization requires us to select a few types of resources to produce heterogeneous classes of products. In the assortment problem addressed here, a resource unit of type j yields, at a cost c_ij, a batch of a_ij product units of type i. The problem, a generalization of the p-median, calls for (i) choosing a restricted subset of resource types and (ii) assigning resource units to products so as to fulfill a given demand vector at a minimum cost. For this problem, we develop a branch-and-price scheme that can either be used to find optimal solutions, or tuned by choosing columns in a suitable class so as to get approximate solutions. The solutions obtained in the second case approach the optimum by a ratio that asymptotically reduces to zero as the demand of the least-required product increases. A comparative analysis of the features of the algorithm is discussed for a wide set of large problem instances.

Key words: deterministic inventory production; integer programming; algorithms; cutting stock; p-median
History: received April 2007; revised December 2007; accepted February 2008.