Skip to main content
Top
Published in:
Cover of the book

2017 | OriginalPaper | Chapter

On the Complexity of Minimizing the Total Calibration Cost

Authors : Eric Angel, Evripidis Bampis, Vincent Chau, Vassilis Zissimopoulos

Published in: Frontiers in Algorithmics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
An edf policy is a schedule in which at any time, the job with the smallest deadline among the available jobs is scheduled first.
 
Literature
3.
go back to reference Fineman, J.T., Sheridan, B.: Scheduling non-unit jobs to minimize calibrations. In: Blelloch, G.E., Agrawal, K. (eds.) Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, 13–15 June 2015, pp. 161–170. ACM (2015). http://doi.acm.org/10.1145/2755573.2755605 Fineman, J.T., Sheridan, B.: Scheduling non-unit jobs to minimize calibrations. In: Blelloch, G.E., Agrawal, K. (eds.) Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, 13–15 June 2015, pp. 161–170. ACM (2015). http://​doi.​acm.​org/​10.​1145/​2755573.​2755605
4.
go back to reference Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287–326 (1979)MathSciNetCrossRefMATH Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287–326 (1979)MathSciNetCrossRefMATH
7.
go back to reference Lueker, G.: Two NP-complete problems in nonnegative integer programming. Report No. 178, Computer Science Laboratory, Princeton University (1975) Lueker, G.: Two NP-complete problems in nonnegative integer programming. Report No. 178, Computer Science Laboratory, Princeton University (1975)
Metadata
Title
On the Complexity of Minimizing the Total Calibration Cost
Authors
Eric Angel
Evripidis Bampis
Vincent Chau
Vassilis Zissimopoulos
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-59605-1_1

Premium Partner