Single item unconstrained lot-sizing with multiple suppliers and minimum order quantities

Question

Variation of the traditional lot-sizing problem - with some additional complexities:

1. multiple suppliers (S1, S2, S3), with different procurement lead-time
2. Suppliers have to be allocated based on a fixed proportion (e.g. 30%, 30%, 40%)
3. Each supplier has a minimum order quantity (MOQ) (e.g. 12, 15, 15)

Rest of the problem is similar to traditional lot-sizing models.

1. Planning horizon of T days
2. No capacity constraints
3. Demand for all T days are known, demand cannot be delayed.
4. Holding (h) and ordering costs(o) are constant over T and also for all suppliers.

I want to check if there are any well known heuristics that allow for fast and close to optimal solutions.

I can use a MILP formulation+solver, but would like to avoid that if possible.

Answer 1

You can get an approximate answer using a genetic algorithm. I tested one (coded in R) using a 30 day horizon, three suppliers with minimum order sizes and shares of the overall orders as above, and with randomly generated demand and cost coefficients and an arbitrary initial inventory. On a small number of test runs, it tended to get within 4% to 6% of the optimal cost (as determined by a MIP model).

I made a few tweaks to your problem. First, I required that every order get split among the three suppliers (so if any supplier receives an order in period $t,$ they all do). Second, to deal with rounding, I allowed the chunk of any order going to a supplier to be at most one unit less than what their percentage of the total order would be. Third, I added a constraint that at the end of the horizon the remaining on-hand inventory plus any inventory in the pipeline (ordered during the planning horizon but not yet delivered) should at least equal the initial inventory. The choice of that limit was arbitrary on my part, but it would be a good idea to set some ending inventory requirement. Otherwise the solution might leave you starting the next planning period with empty shelves.

The GA uses a binary chromosome with one bit for each period, where a 1 signals that an order will be placed and a 0 signals no order. Prior to running the GA, we compute the last possible time $\bar{t}$ for the first order placed (the last time such that the fastest supplier could make a delivery before any demand was lost). Given a chromosome, we repair it if necessary by setting the bit at position $\bar{t}$ to 1 if no prior bit is 1. Now that we know the order dates (and the total ordering cost), we compute order quantities using a "Just In Time" approach to minimize holding costs. For each order date except the last, we compute the smallest combined order quantity such that, after allocating to suppliers and if necessary boosting it so that all suppliers have their minimum order limit met, no demand is lost prior to the earliest delivery date of the next order. For the final order, we tweak the quantity to also ensure that ending inventory plus orders in the pipeline meet the terminal criterion.

Answer 2

You could try my online solver for single-item capacitated economic lot sizing and use it 3 times (for each supplier once) and use as demand the proportion (30%, 30%, 40%) of the demand rounded to the closest integer. For the values in the column "up" use the values 11, 14 and 14 (=MOQ-1). All input data must be integer. Here is sample input data, see how the solution changes when you change 14 to 15:

I u_o y_o y_I
6; 0; 0; 0;
startup x_min fix  var  up  fix var x_max demand y_min fix var y_max
   0;     0; 9999;  0,  14,  0,  1, 9999;   10;    0;   0,  1, 9999;
   0;     0; 9999;  0,  14,  0,  1, 9999;   10;    0;   0,  1, 9999;
   0;     0; 9999;  0,  14,  0,  1, 9999;   10;    0;   0,  1, 9999;
   0;     0; 9999;  0,  14,  0,  1, 9999;   10;    0;   0,  1, 9999;
   0;     0; 9999;  0,  14,  0,  1, 9999;   10;    0;   0,  1, 9999;
   0;     0; 9999;  0,  14,  0,  1, 9999;   10;    0;   0,  1, 9999;