1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Do your fixed proportions (30/30/40) apply to all individual orders, or just to the total amount ordered over the time horizon? $\endgroup$
    – prubin
    Feb 28, 2023 at 16:25
  • $\begingroup$ In the more general case it would be over a period of time, like a financial quarter. In the current case, we do the split per individual order. $\endgroup$
    – anerjee
    Mar 1, 2023 at 6:23
  • $\begingroup$ @anerjee, do you hear about the MRP-II (manufacturing resource planning) algorithm? The best heuristic-based decomposition method to solve the production planning models also, consists of lot-sizing. $\endgroup$
    – A.Omidi
    Mar 1, 2023 at 12:31
  • $\begingroup$ Are your demand quantities integers? $\endgroup$
    – prubin
    Mar 1, 2023 at 17:14
  • $\begingroup$ demand quantities are integers $\endgroup$
    – anerjee
    Mar 3, 2023 at 3:17

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.