The weighted sum of split and diameter clustering

In this paper, we propose a bicriterion objective function for clustering a given set ofN entities, which minimizes [d–(1–)s], where 01, andd ands are the diameter and the split of the clustering, respectively. When =1, the problem reduces to minimum diameter clustering, and when =0, maximum split clustering. We show that this objective provides an effective way to compromise between the two often conflicting criteria. While the problem is NP-hard in general, a polynomial algorithm with the worst-case time complexityO(N ²) is devised to solve the bipartition version. This algorithm actually gives all the Pareto optimal bipartitions with respect to diameter and split, and it can be extended to yield an efficient divisive hierarchical scheme. An extension of the approach to the objective [(d ₁+d ₂)–2(1–)s] is also proposed, whered ₁ andd ₂ are diameters of the two clusters of a bipartition.This research was supported in part by the National Science and Engineering Research Council of Canada (Grant OGP 0104900). The authors wish to thank two anonymous referees, whose detailed comments on earlier drafts improved the paper.     

Sequencing deliveries to minimize inventory holding cost with dominant upstream supply chain partner

This paper studies a two stage supply chain with a dominant upstream partner. Manufacturer is the dominant partner and operates in a Just-in-Time environment. Production is done in a single manufacturing line capable of producing two products without stopping the production for switching from one product to the other. The manufacturer imposes constraints on the distributor by adhering to his favorable production schedule which minimizes his manufacturing cost. Distributor on the other hand caters to retailers' orders without incurring any shortages and is responsible for managing the inventory of finished goods. Adhering to manufacturer's schedule may lead to high inventory carrying costs for the distributor. Distributor's problem, which is to find an optimal distribution sequence which minimizes the distributor's inventory cost under the constraint imposed by the manufacturer is proved NP-Hard by Manoj et al. (2008). Therefore, solving large size problems require efficient heuristics. We develop algorithms for the distribution problem by exploiting its structural properties. We propose two heuristics and use their solutions in the initial population of a genetic algorithm to arrive at solutions with an average deviation of less than 3.5% from the optimal solution for practical size problems.