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

Khadija Hadj Salem (), Vincent Jost, Yann Kieffer, Luc Libralesso and Stéphane Mancini
Additional contact information
Khadija Hadj Salem: Université de Tours, LIFAT EA 6300, CNRS, ROOT ERL CNRS 7002
Vincent Jost: Univ. Grenoble Alpes, Grenoble INP, GSCOP
Yann Kieffer: Univ. Grenoble Alpes, Grenoble INP, LCIS
Luc Libralesso: Univ. Grenoble Alpes, Grenoble INP, GSCOP
Stéphane Mancini: Univ. Grenoble Alpes, Grenoble INP, TIMA

Operational Research, 2022, vol. 22, issue 3, No 1, 1639-1673

Abstract: 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.

Keywords: Embedded vision systems; Scheduling; Makespan; Integer linear programming; Constraint programming; Greedy algorithms; LocalSolver; Simulated annealing; Beam search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-021-00647-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:22:y:2022:i:3:d:10.1007_s12351-021-00647-0

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-021-00647-0

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().