Optimizing production program

Question

As part of the production of masscustomization products, I have to solve the following problem. A fixed set of sequences (changes from one product to another) is associated with a percentage value of quality defects each. Now my goal is to find the optimal order (by minimizing the quality defects) in which to manufacture a fixed set of products in a particular week.

For example, I have to produce 4 different products (each manufactured X times): Changes from A to A leads in average to 5% scrap products. Change from Product A to B normally leads to 5 percent scrap parts, B to A to 10% scrap, B to C to 7.5% scrap and so on. As I stated above the overall objective would be to minimize the total scrap (error) products.

I'm unsure how to formulate this as an optimization problem properly. In university I heard something about the viterbi algorithm. Is this applicable here or how would I approach such a task?

Answer 1

This sounds like the shortest path problem. If you have an object of type $A$ and you need to convert it to object of type $D$, you are effectively asking if it is better to first convert it to $B$ or to $C$ as an intermediate step. So, just fill in the matrix of losses from each element to each, and then solve for the shortest path using any algorithm you like. Viterbi seems like a stochastic algorithm, but in your case the problem is quite deterministic, so something as simple as Dijkstra's would work fine. Just pay attention that your losses are multiplicative. If after every operation you are left with a remainder fraction $R$, then the total remainder will be the multiplicative

$$R_{tot} = R_{AB} * R_{BC} * R_{CD}$$

and your loss will be

$$L = 1 - R_{tot} = 1 - R_{AB} * R_{BC} * R_{CD}$$

Normally shortest path algorithms work with additive losses, so we need to do some math here in order to convert our problem to additive losses.

1. Note that minimizing loss is the same as maximizing $R_{tot}$
2. Maximizing $R_{tot}$ is the same as maximizing $\log R_{tot}$ or minimizing -$\log R_{tot}$. We use logarithm because logarithm of a product is a sum of logarithms - super useful to convert multiplication to addition.

Thus, let $\epsilon=-\log R$. We want to minimize the following additive quantity

$$\epsilon_{tot} = \epsilon_{AB} + \epsilon_{BC} + \epsilon_{CD}$$

So you will need to fill your shortest path matrix not directly with losses, but with their negative logarithms. For example, if $A$ to $B$ incurs 5% loss, then $R_{AB} = 0.95$ and $\epsilon_{AB} = -\log_e R_{AB} \approx 0.051$. I have used natural logarithm, but the base is irrelevant as long as you are consistent