A production line consists of an ordered sequence of 𝑛 production stages, and each stage
has a manufacturing operation followed by a potential inspection. The product enters stage 1
of the production line in batches of size 𝐵 > 1. As the items within a batch move through
the manufacturing stages, the operations might introduce defects.
The probability of producing a defect at stage 𝑖 is ai. We assume that all the defects are nonrepairable,
so we must scrap any defective item. After each stage, we can either inspect all
the items or none of them (we do not sample the items); we assume that the inspection
identifies every defective item. The production line must end with an inspection station so
that we do not ship any defective units.
Further, we have the cost data available:
(1) 𝑃! , the manufacturing cost per unit in stage 𝑖.
(2) 𝑓!", the fixed cost of inspecting a batch after stage 𝑗, given that we last inspected the
batch after stage 𝑖.
(3) 𝑔!", the variable per unit cost for inspecting an item after stage 𝑗, given that we last
inspected the batch after stage 𝑖.
Our decision problem is to find an optimal inspection plan that specifies at which stages we
should inspect the items so that we minimize the total cost of production and inspection.
Using fewer inspection stations might decrease the inspection costs, but will increase the
production costs because we might perform unnecessary manufacturing operations on some
units that are already defective. The optimal number of inspection stations will achieve an
appropriate trade-off between these two conflicting cost considerations.
Hint: this problem can be solved by finding a shortest path in a graph where the nodes are
stages, and there are appropriate weights on the edges.
Implement an appropriate shortest path algorithm for this problem with minimal time
complexity. Assume that all costs are positive. Your program should take the costs as input
from a file with the following format.
Your output should be the list of indices where inspection stations should be placed.
Submission instruction:
Submit a c / python file with the code