---

The Supply Management Problem with Lower-Bounded Demands (SMPLD) was initially formulated in (Chauhan et al., 2004). In this problem a set of providers supply product of one type to a set of consumers, the quantity of product that can be delivered lies between the given minimum and maximum values, and the costs proposed by each provider are linear functions of the quantity being delivered if the shipment is opened. The SMPLD consists in ¯nding the quantity of product which will be supplied by each provider to each consumer minimizing the total cost The mathematical formulation of SMPLD is:

Here m is the number of suppliers; n is the number of consumers; variables z_ij indicate the presence of delivery from a provider i to a consumer j, while x_ij represent the shipment size. A_j is the minimal amount of product required for the consumer j; m_ij is the minimum quantity the provider i is prepared to deliver to the consumer j; M_i is the maximum quantity the provider i is able to deliver in total. Parameters a_ij; c_ij; m_ij; M_i; A_j are supposed to be nonnegative and integer, although the integrality is not essential in this paper.

Many practical problems in logistics, scheduling and production planning can be modeled as SMPLD or contain it as an important special case { see e.g. (Sun et al., 1998; Sheng et al., 2006).

In case all m_ij = 0 and the overall supply is equal to the overall demand, i.e.

this problem becomes the well-known Fixed Charge Transportation Problem (FCTP) - see e.g. (Barr et al., 1981; Sun et al., 1998).

The SMPLD is also closely related to the supply management problem (SMP) considered by Chauhan and Proth (2003) and Chauhan et al. (2005a). The first difference between SMP and SMPLD is that instead of inequality (2), in the SMP holds an equality

The second di®erence is that in the SMP the cost functions are more general, namely, non-decreasing and concave. Finding any feasible solution to the SMP is NP-hard even for n = 1, yet there exists a pseudopolynomial-time exact algorithm for it (Chauhan et al., 2005a).

The SMPLD is also NP-hard (it contains the minimum knapsack problem as a special case) and finding a feasible solution satisfying (2){(5) is NP-hard even in the case n = 2. However, in case n = 1, this problem admits a fully polynomial time approximation scheme (FPTAS) and there is a fast greedy 2-approximation algorithm for it (Chauhan et al., 2004). An FPTAS for n = 1 and more general form of the cost functions is developed in (Chauhan et al., 2005b). At the same time, in the SMPLD, unlike SMP, consumption of goods is not given in advance, but only bounded from below, thus yielding larger linear relaxation polyhedron.

References

1. Barr, R.S., R.S. Glover and D. Klingman (1981). A new optimization method for large scale fixed charge transportation problems. Oper. Res. 29(3), 448–463.

2. Chauhan, S.S. and J.-M. Proth (2003). The concave cost supply problem. Europ. Journ. of Oper. Res. 148(2), 374–383.

3. Chauhan, S.S., A.V. Eremeev, A.A. Kolokolov and V.V. Servakh (2005a). Concave cost supply management problem for single manufacturing unit. In: Supply Chain Optimisation, Product/Process Design, Facility Location and Flow Control (A. Dolgui, J. Soldek and O. Zaikin, Eds.). Springer Verlag. pp. 167–174.

4. Chauhan, S.S., A.V. Eremeev, A.A. Romanova and V.V. Servakh (2004). Approximation of linear cost supply management problem with lower-bounded demands. In: Proc. of Discrete Optimization Methods in Production and Logistics (DOM`2004). pp. 16–21. Omsk.

Home