Minimizing the number of workers in a paced mixed-model assembly line

Xavier Delorme 1, 2 Alexandre Dolgui 3, 4, 5 Sergey Kovalev 6 Mikhail Kovalyov 7
1 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
2 Mines Saint-Étienne MSE - École des Mines de Saint-Étienne
3 IMT Atlantique - IMT Atlantique Bretagne-Pays de la Loire
4 DAPI - Département Automatique, productique et informatique
5 SLP - Systèmes Logistiques et de Production
LS2N - Laboratoire des Sciences du Numérique de Nantes
6 INSEEC Business School - Institut des hautes études économiques et commerciales Business School (INSEEC)
7 NASB - National Academy of Sciences of Belarus
Abstract : We study a problem of minimizing the maximum number of identical workers over all cycles of a paced assembly line comprised of m stations and executing n parts of k types. There are lower and upper bounds on the workforce requirements and the cycle time constraints. We show that this problem is equivalent to the same problem without the cycle time constraints and with fixed workforce requirements. We prove that the problem is NP-hard in the strong sense if and the workforce requirements are station independent, and present an Integer Linear Programming model, an enumeration algorithm and a dynamic programming algorithm. Polynomial in k and polynomial in n algorithms for special cases with two part types or two stations are also given. Relations to the Bottleneck Traveling Salesman Problem and its generalizations are discussed.
Keywords : algorithms production line computational complexity workforce assignment
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2019, 272 (1), pp.188 - 194. 〈10.1016/j.ejor.2018.05.072〉
Liste complète des métadonnées

Littérature citée [48 références]  Voir  Masquer  Télécharger
https://hal-emse.ccsd.cnrs.fr/emse-01840007
Contributeur : Florent Breuil <>
Soumis le : lundi 16 juillet 2018 - 13:52:43
Dernière modification le : jeudi 7 février 2019 - 14:53:37
Document(s) archivé(s) le : mercredi 17 octobre 2018 - 14:37:18

Fichier

WorkersTSP 9 March.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

EMSE | PRES_CLERMONT | IMT-ATLANTIQUE | LS2N | UNAM | INSTITUT-TELECOM | LIMOS | SIGMA-CLERMONT | DEMO-ENSMSE | FAYOL-ENSMSE | UNIV-NANTES | LS2N-SLP

Citation

Xavier Delorme, Alexandre Dolgui, Sergey Kovalev, Mikhail Kovalyov. Minimizing the number of workers in a paced mixed-model assembly line. European Journal of Operational Research, Elsevier, 2019, 272 (1), pp.188 - 194. 〈10.1016/j.ejor.2018.05.072〉. 〈emse-01840007〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

85

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD