Assembly line feeding problem

The assembly line feeding problem (abbr. ALFP) describes a problem in operations management concerned with finding the optimal way of feeding parts to assembly stations. For this, various cost elements may be taken into account and every part is assigned to a policy, i.e., a way of feeding parts to an assembly line. The most common policies are:

• Line stocking (also: line side stocking, pallet to work-station, etc)
• Boxed-supply (also: Kanban, batch supply, etc.)
• Sequencing
• Stationary kitting (also: indirect supply, trolley to workstation)
• Traveling kitting (also: indirect supply, kit to assembly line)

These policies differ with respect to the way parts are brought to the line as well as in the way parts are handled before they are brought to the line. E.g., in line stocking, parts are brought to the line directly in the way they are stored in the warehouse. In the other policies, quantities are reduced (boxed supply) and different part variants are sorted in the order of demand (sequencing, stationary, and traveling kitting).

History

The problem was formally introduced by Bozer and McGinnis in 1992 by means of a descriptive cost model. Since then, many contributions have been made in both, quantitative and qualitative manners. E.g., a more qualitative contribution is done by Hua and Johnson investigating important aspects of the problem, whereas more recent contributions focus rather on quantitative aspects and use mathematical optimization to solve this assignment problem to optimality

Mathematical problem statement

$\begin{array}{c}\text{minimize:}\\ C& =\sum _{i\in I}\sum _{s\in S}\sum _{p\in P}{\chi }_{isp}\cdot c_{isp}^v+\sum _{s\in S}\sum _{p\in P}{\psi }_{sp}\cdot c_{sp}^f+\sum _{p\in P}{\Omega }_p\cdot c_p^f\\ \text{subject to:}\\ \sum _{p\in P}{\chi }_{isp}& =min\{1,{\lambda }_{is}\}& \mathrm{\forall }& i\in I\mathrm{\forall }s\in S\\ \underset{i\in I}{\max }\{{\chi }_{isp}\}& \le {\psi }_{sp}& \mathrm{\forall }& s\in S\mathrm{\forall }p\in P\\ \underset{i\in I,s\in S}{\max }\{{\chi }_{isp}\}& \le {\Omega }_p& \mathrm{\forall }& p\in P\\ {\chi }_{isp}& \in \{0,1\}& \mathrm{\forall }& i\in I\mathrm{\forall }s\in S\mathrm{\forall }p\in P\\ {\psi }_{sp}& \in \{0,1\}& \mathrm{\forall }& s\in S\mathrm{\forall }p\in P\\ {\Omega }_p& \in \{0,1\}& \mathrm{\forall }& p\in P\end{array}$

This model minimizes the costs $c_{isp}$ when assigning all parts (index:i) to a feeding policy (index:p) at all stations (index:s) ${\chi }_{isp}=1$, if there is a demand for a part at a station ${\lambda }_{is}>0$. Using a certain policy at a station ${\psi }_{sp}=1$ incurs some cost $c_{sp}$ as well as some other costs $c_p$ are incurred when a policy is used at any station, ${\Omega }_p=1$.

All assembly line feeding problems of this type have been proven to be NP-hard