Lot-sizing on a single imperfect machine: ILP models and FPTAS extensions

Kseniya Schemeleva 1, 2, 3 Xavier Delorme 4 Alexandre Dolgui 4 Frédéric Grimaud 1, 2 Mikhail Y. Kovalyov 5
1 DEMO-ENSMSE - Département Décision en Entreprise : Modélisation, Optimisation
2 LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes
3 IDRAC - IDRAC - Center of Applied Research
4 Laboratoire en Sciences et Technologies de l'Information
LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes, DEMO-ENSMSE - Département Décision en Entreprise : Modélisation, Optimisation
5 NATIONAL ACADEMY OF SCIENCES OF BELARUS - National Academy of Sciences of Belarus
Abstract : A single-machine multi-product lot-sizing and sequencing problem is studied. In this problem, items of n different products are manufactured in lots. Demands for products as well as per item processing times are known. There are losses of productivity because of non perfect production. There is also a sequence dependent set-up time between lots of different products. Machine yields and product lead times are assumed to be known deterministic functions. The objective is to minimize the cost of the demand dissatisfaction provided that the total processing time does not exceed a given time limit. We propose two integer linear programming (ILP) models for the NP-hard "fraction defective" case of this problem and compare effectiveness of their ILOG CPLEX realizations with a dynamic programming algorithm in a computer experiment. We also show how an earlier developed fully polynomial time approximation scheme (FPTAS) and one of the ILP models can be extended for a more complex case.
Keywords : Lot-sizing Sequencing Imperfect production FPTAS Integer linear program
Type de document :
Article dans une revue
Computers and Industrial Engineering, Elsevier, 2013, Volume 65 (Issue 4), pp.Pages 561-569. 〈10.1016/j.cie.2013.04.002〉
Liste complète des métadonnées
https://hal-emse.ccsd.cnrs.fr/emse-00881337
Contributeur : Florent Breuil <>
Soumis le : vendredi 8 novembre 2013 - 09:54:13
Dernière modification le : dimanche 28 janvier 2018 - 15:22:05

Identifiants

Collections

EMSE | DEMO-ENSMSE | FAYOL-ENSMSE | LIMOS | PRES_CLERMONT | TDS-MACS | SIGMA-CLERMONT

Citation

Kseniya Schemeleva, Xavier Delorme, Alexandre Dolgui, Frédéric Grimaud, Mikhail Y. Kovalyov. Lot-sizing on a single imperfect machine: ILP models and FPTAS extensions. Computers and Industrial Engineering, Elsevier, 2013, Volume 65 (Issue 4), pp.Pages 561-569. 〈10.1016/j.cie.2013.04.002〉. 〈emse-00881337〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

162

Contact

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