Skip to Main content Skip to Navigation
Journal articles

Minimizing makespan under data prefetching constraints for embedded vision systems: a study of optimization methods and their performance

Khadija Hadj Salem 1 Vincent Jost 2 Yann Kieffer 3 Luc Libralesso 2 Stéphane Mancini 4
2 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
4 CDSI - Circuits, Devices and System Integration
TIMA - Techniques de l'Informatique et de la Microélectronique pour l'Architecture des systèmes intégrés
Abstract : In confronting the “Memory Wall”, the design of embedded vision systems exhibits many challenges regarding design cost, energy consumption, and performance. This paper considers a variant of the Job Shop Scheduling Problem with tooling constraints, arising in this context, in which the completion time (makespan) is to be minimized. This objective corresponds to the performance of the produced circuit. We discuss different formulations using integer linear programming and point out their characteristics, namely the size and the quality of the linear programming relaxation bound. To solve this scheduling problem with large size, we compare various approaches, including a Constraint Programming model, two constructive greedy heuristics, two models of LocalSolver, a Simulated Annealing algorithm, and a Beam Search algorithm. Numerical experiments are conducted on 16 benchmark instances from the literature and 12 real-life non-linear image processing kernels for validating their efficiency.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03010229
Contributor : Khadija Hadj Salem Connect in order to contact the contributor
Submitted on : Thursday, May 27, 2021 - 10:16:56 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:39 AM

File

ORIJ2019_FullPaper_Published.p...
Files produced by the author(s)

Identifiers

Citation

Khadija Hadj Salem, Vincent Jost, Yann Kieffer, Luc Libralesso, Stéphane Mancini. Minimizing makespan under data prefetching constraints for embedded vision systems: a study of optimization methods and their performance. Operational Research, Springer, 2021, ⟨10.1007/s12351-021-00647-0⟩. ⟨hal-03010229v2⟩

Share

Metrics

Record views

153

Files downloads

251