Approximate solutions for a special pagination problem with 2 symbols per tile
Aristide Grange, Imed Kacem, Sébastien Martin, Sarah Minich · 2021 IEEE International Conference on Networking, Sensing and Control (ICNSC) · 2021
In this paper, we consider a special pagination problem, where we have to assign a set of tiles (or jobs) on two pages (or machines), with the aim of minimizing the used space (or makespan) of the most workloaded page. The specificity of this problem consists in the fact that every tile is composed of two symbols. Moreover, a given symbol can be shared by two (or more) tiles. Thus, the problem is related to two fields: scheduling and graph theory. Given its NP-hardness, we propose different approximate algorithms and we analyse their effectiveness on a large set of instances. The obtained results are promising.