Finance:Assembly line feeding problem

From HandWiki

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..[1] 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).


The problem was formally introduced by Bozer and McGinnis[2] 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[3] 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 [4][5][6][7]

Mathematical problem statement

[math]\displaystyle{ \begin{align} \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}\} &\forall &i \in I~\forall s \in S \\ \underset{i \in I}{\operatorname{max}}~\{\chi_{isp}\} &\leq \psi_{sp} &\forall &s \in S~\forall p \in P \\ \underset{i \in I, s \in S}{\operatorname{max}}~\{\chi_{isp}\} &\leq \Omega_{p} &\forall &p \in P \\ \chi_{isp} &\in \{0,1\} &\forall &i \in I~\forall s \in S~\forall p \in P \\ \psi_{sp} &\in \{0,1\} &\forall &s \in S~\forall p \in P \\ \Omega_{p} &\in \{0,1\} &\forall &p \in P \end{align} }[/math]

This model minimizes the costs [math]\displaystyle{ c_{isp} }[/math] when assigning all parts (index:i) to a feeding policy (index:p) at all stations (index:s) [math]\displaystyle{ \chi_{isp}=1 }[/math], if there is a demand for a part at a station [math]\displaystyle{ \lambda_{is}\gt 0 }[/math]. Using a certain policy at a station [math]\displaystyle{ \psi_{sp}=1 }[/math] incurs some cost [math]\displaystyle{ c_{sp} }[/math] as well as some other costs [math]\displaystyle{ c_{p} }[/math] are incurred when a policy is used at any station [math]\displaystyle{ \omega_{p}=1 }[/math].

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


  1. 1.0 1.1 Schmid, Nico, André; Limère, Veronique (2019). "A classification of tactical assembly line feeding problems". International Journal of Production Research: 1–24. doi:10.1080/00207543.2019.1581957. 
  2. Bozer, Yavuz A.; McGinnis, Leon F. (1992). "Kitting versus line stocking: A conceptual framework and a descriptive model". International Journal of Production Economics 28: 1–19. doi:10.1016/0925-5273(92)90109-K. 
  3. Hua, Stella Y.; Johnson, Danny J. (2010). "Research issues on factors influencing the choice of kitting versus line stocking". International Journal of Production Research 48 (3): 779–800. doi:10.1080/00207540802456802. 
  4. Limère, Veronique; Van Landeghem, Hendrik; Goetschalckx, Marc (2015). "A decision model for kitting and line stocking with variable operator walking distances". Assembly Automation 35 (1): 47–56. doi:10.1108/AA-05-2014-043. 
  5. Sternatz, Johannes (2015). "The joint line balancing and material supply problem". International Journal of Production Economics 159: 304–318. doi:10.1016/j.ijpe.2014.07.022. 
  6. Sali, Mustapha; Sahin, Evren (2016). "Line feeding optimization for Just in Time assembly lines: An application to the automotive industry". International Journal of Production Economics 174: 54–67. doi:10.1016/j.ijpe.2016.01.009. 
  7. Schmid, Nico André; Limère, Veronique; Raa, Birger (2018). "Modeling variable space in assembly line feeding". IFAC PapersOnLine 51 (11): 164–169. doi:10.1016/j.ifacol.2018.08.252.