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

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 <>
Submitted on : Thursday, May 27, 2021 - 10:16:56 AM
Last modification on : Monday, July 26, 2021 - 4:40:49 PM

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

81

Files downloads

120