On the complexity of minimizing the total calibration cost - Université Pierre et Marie Curie Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

On the complexity of minimizing the total calibration cost

Evripidis Bampis
  • Fonction : Auteur
  • PersonId : 855947
Vincent Chau
  • Fonction : Auteur
  • PersonId : 931462
Vassilis Zissimopoulos
  • Fonction : Auteur
  • PersonId : 954050

Résumé

Bender et al. (SPAA 2013) proposed a theoretical framework for testing in contexts where safety mistakes must be avoided. Testing in such a context is made by machines that need to be often calibrated. Since calibrations have non negligible cost, it is important to study policies minimizing the calibration cost while performing all the necessary tests. We focus on the single-machine setting and we study the complexity status of different variants of the problem. First, we extend the model by considering that the jobs have arbitrary processing times and that the preemption of jobs is allowed. For this case, we propose an optimal polynomial time algorithm. Then, we study the case where there is many types of calibrations with different lengths and costs. We prove that the problem becomes NP-hard for arbitrary processing times even when the preemption of the jobs is allowed. Finally, we focus on the case of unit-time jobs and we show that a more general problem, where the recalibration of the machine is not instantaneous, can be solved in polynomial time.
Fichier principal
Vignette du fichier
Angel2017.pdf (195.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01630651 , version 1 (18-08-2022)

Licence

Paternité

Identifiants

Citer

Eric Angel, Evripidis Bampis, Vincent Chau, Vassilis Zissimopoulos. On the complexity of minimizing the total calibration cost. 11th International Frontiers of Algorithmics Workshop (FAW 2017), Jun 2017, Chengdu, China. pp.1--12, ⟨10.1007/978-3-319-59605-1_1⟩. ⟨hal-01630651⟩
373 Consultations
35 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More