A modified particle swarm optimisation algorithm to solve the part feeding problem at assembly lines

Abstract

The Assembly Line Part Feeding Problem (ALPFP) is a complex combinatorial optimisation problem concerned with the delivery of the required parts to the assembly workstations in the right quantities at the right time. Solving the ALPFP includes simultaneously solving two sub-problems, namely tour scheduling and tow-train loading. In this article, we first define the problem and formulate it as a multi-objective mixed-integer linear programming model. Then, we carry out a complexity analysis, proving the ALPFP to be NP-complete. A modified particle swarm optimisation (MPSO) algorithm incorporating mutation as part of the position updating scheme is subsequently proposed. The MPSO is capable of finding very good solutions with small time requirements. Computational results are reported, demonstrating the efficiency and effectiveness of the proposed MPSO.

Keywords:

• part feeding problem
• assembly line
• tour scheduling
• tow-train loading
• particle swarm optimisation

Acknowledgements

The authors greatly appreciate the collaboration of Volkswagen Navarra, the department of logistics in particular, as well as the Volkswagen Chair Universidad de Navarra for partially funding this research. The authors would like to thank Prof. Dr. Nils Boysen from Friedrich Schiller University Jena for his valuable comments and suggestions to improve the quality of the paper.

Notes

1. Tow-train capacity is transformed into tour capacity by adding the capacity of all available tow-trains. Thus, here and hereafter, when referring to capacity limits, tour and tow-train will be used interchangeably.

2. Hereafter, we will use priority rules or heuristic interchangeably.

Additional information

Funding

This work was also partially funded by the Basque government under project named ‘Saiotek: MEPLAM’, and Energy-Aware Feeding Systems Project (EASY), an ERA-NET project of the ECO-INNOVERA 1st Joint Call, as well as the project ‘NORTE-07-0124-FEDER-000057’, funded by the North Portugal Regional Operational Programme (ON.2 - O Novo Norte), under the National Strategic Reference Framework (NSRF), through the European Regional Development Fund (ERDF); by ERDF (FEDER) through the COMPETE Programme, and by national funds, through the Portuguese funding agency, Fundação para a Ciência e a Tecnologia (FCT) within project FCOMP-01-0124-FEDER-037281.