Optimization of resources allocation

Question

Simplified problem:

Let's say we sell chicken. There are an order for today for 10 pieces from KFC that requires chicken to be good for at least 1 month and an order for tomorrow for 5 pieces from McDonald’s, that requires chicken to be good for at least 3 month. We have 6 pieces of chicken on stock with expiration date of 1 month and 12 pieces of 3 month. How to complete KFC's order with worst possible chicken (that pass the requirement) enabling completing MD order tomorrow?

Additional information:

• we are interested only in today's and tomorrow's orders;
• number of orders can vary (we need to optimize only orders for today);
• number of requirement can vary (for example 1) expiration date 2) production date)
• optimization applies to only one known requirement;
• it's not possible to divide piece of chicken into fractional pieces;
• it's not possible to sell negative amount of chicken.

I tried to build a system of linear inequalities, for example:

\begin{cases} KFC_{1m} + KFC_{3m} = 10 \\ MD_{3m} = 5 \\ KFC_{1m} \leq 6 \\ KFC_{3m} + MD_{3m} \leq 12 \\ \end{cases}

So the answer is: \begin{cases} KFC_{1m} = 6 \\ KFC_{3m} = 4 \\ \end{cases}

In this case it's easy to find a solution by hand, but for large systems it's not possible. I was thinking about extrapolating my logic to a general form like: \begin{cases} \sum_{i=1}^{n} X_{1i} = C_{1} \\ \sum_{i=1}^{n} X_{2i} = C_{2} \\ ... \\ \sum_{i=1}^{n} X_{mi} = C_{m} \\ \sum_{i=1}^{m} X_{i1} \leq K_{1} \\ \sum_{i=1}^{m} X_{i2} \leq K_{2} \\ ... \\ \sum_{i=1}^{m} X_{in} \leq K_{n} \\ \end{cases}

• $m$ is the amount of total orders (today + tomorrow);
• $n$ is the amount of different stock items;
• $X$ represents amount of a stock item for given order, for example $X_{11}$ is the amount of the first stock item for the first order, $X_{12}$ is the amount of the second stock item for the first order etc. Some of $X$ would be zero at the begging if a stock item doesn't pass the requirements for the order;
• $C_{p}$ is the ordered amount for $p$th order;
• $K_{p}$ is the total available amount of $p$th item (for example total amount of chicken with expiration date of 1 month is 12);
• we can also assume that $(k-1)$th stock item is worse than $k$th stock item (chicken with exp. date of 1m is worse than a chicken with 3m).

So the goal is to find a solutions for first $x$ orders with the worst possible stock items used and also enable completion of the other orders.

I tried to apply some of the lp. algorithms, but had no success, any thoughts?

P.S. I appreciate any feedback on improving the question.

Answer 1

I propose the following greedy approach. We don't distinguish orders by date (today or tomorrow) or by customer, but we split each order into pieces by items. Then we sum them up by each item. Let $y_{ij}$ be the order of $i$-th customer for $j$-th item. (And it is fine to give them some pieces of $k$-th item for any $k \ge j$.) So we have the total order of $s_1 = \sum_i y_{i1}$ of the first item, $s_2 = \sum_i y_{i2}$ of the second item and so on, $s_j = \sum_i y_{ij}$ of the $j$-th item.

It is obvious that we have to sell at least $s_n$ pieces of $n$-th item. Distribute them among all orders with positive $y_{in}$. Remaining $K_n - s_n$ pieces we put into stack. Or let's complicate the process a bit. We firstly put all $K_n$ pieces into stack and then take $s_n$ of them from the top of the stack. Now consider demand on $s_{n - 1}$ pieces of $(n - 1)$-th item. We put $K_{n - 1}$ pieces of $(n - 1)$-th item into stack and take $s_{n - 1}$ pieces from the top of the stack. It means that if $s_{n - 1} \le K_{n - 1}$ then we will take only $(n - 1)$-th item. But if $s_{n - 1} > K_{n - 1}$ we will also take minimum possible amount of $n$-th item. And so on.

So the algorithm is the following. For each $j$ from $n$ downto $1$ we put $K_j$ pieces of $j$-th item into stack and then take $s_j$ pieces from the top of the stack. (To be more precise here we could put an inner cycle which takes $y_{ij}$ pieces from the top of the stack and adds it to $i$-th order for each $i$ from $1$ to $m$.) If at some point we try to take a piece from an empty stack, then it is impossible to proceed all orders. Otherwise at the end we save the best set of pieces, i. e., we maximize the number of $n$-th item pieces, among sets with the same number of $n$-th item pieces we maximize the number of $(n - 1)$-th item pieces and so on.