Economic lot scheduling problem
Le problème connu sous le nom de economic lot scheduling problem (ELSP) est un problème du domaine de la recherche opérationnelle. Le terme est utilisé pour décrire un cas dérivé de la formule de Wilson : Celui-ci est seulement concerné avec la quantité optimale d'un produit à commander pour le ré-approvisionnement d'un magasin. Avec ELSP, la machine de production peut fabriquer plusieurs produits, un type de produit à la fois. La question est de savoir quelle quantité de quel produit il fait produire, et dans quel ordre les produits doivent être fabriqués. Le changement d'un type de produit à un autre entraine des coûts.
La première formulation du problème ELSP date de 1958[1].
ELSP est un modèle mathématique d'un problème connue par la plupart des compagnies et industries : la planification de la production.
Difficultés
Le problème est bien connu de la communauté de la recherche opérationnelle. La plupart des publications se penchent sur des aspects du problème, comment le résoudre en général, et pour des cas particuliers.
Le problème est connue comme étant difficile : à ce moment, il n'est pas possible de trouver une solution optimale sans regarder la quasi-totalité des possibilités. De ce fait le problème est dans la classe de complexité NP-hard.
Deux approches ont été tentés pour le moment : premièrement, de restreindre la solution à un type spécifique, ce qui rend possible de trouver la solution optimale pour ce type restreint. Deuxièmement, des heuristiques ou des algorithmes génétiques sont utilisés pour approcher de la solution optimale.
Références
- Jack D. Rogers : A Computational Approach to the Economic Lot Scheduling Problem, Management Science, Vol. 4, No. 3, avril 1958, pp. 264–291
Publications
- S E Elmaghraby: The Economic Lot Scheduling Problem (ELSP): Review and Extensions, Management Science, Vol. 24, No. 6, février 1978, pp. 587–598
- M A Lopez, B G Kingsman: The Economic Lot Scheduling Problem: Theory and Practice, International Journal of Production Economics, Vol. 23, , pp. 147–164
- Michael Pinedo, Planning and Scheduling in Manufacturing and Services, Springer, 2005. (ISBN 0-387-22198-0)
- Jack D. Rogers: A Computational Approach to the Economic Lot Scheduling Problem, Management Science, Vol. 4, No. 3, April 1958, pp. 264–291