Geodesic
Walk on the Hypercube with Minimum Similarities
Serdica Journal of Computing, Tome 16 (2023) no. 1, pp. 57-70.

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

An efficient scheduler (algorithm) as a part of batch processing, implemented in a real warehouse management system is considered. The goal is not completion time but rather the fairness of the schedule expressed as a minimal overload of working places (machines, workers, etc.) used. As a combinatorial optimization problem, the objective is to find the permutation of the rows of a n x k boolean matrix B that minimizes the sum of the scalar products of each two consecutive rows. For the above-mentioned warehouse, the size n of a batch is in thousands and the number of working places is up to ten. The problem is modeled as many visits traveling salesman problem over the vertices of k dimensional unit hypercube with distances equal to the scalar products of the coordinate vectors of the vertices. The case n= 2^k is proven NP-hard and for the needs of the practice, where n >> k a heuristic greedy algorithm with a good, experimentally proven precision is proposed.
Keywords: Scheduling, Travelling Salesman Problem, Transportation Problem, Integer Programming 
@article{SJC_2023_16_1_a0,
     author = {Georgiev, Georgi and Yanev, Nicola and Kelevedjiev, Emil and Yurukov, Borislav},
     title = {Walk on the {Hypercube} with {Minimum} {Similarities}},
     journal = {Serdica Journal of Computing},
     pages = {57--70},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2023_16_1_a0/}
}
TY  - JOUR
AU  - Georgiev, Georgi
AU  - Yanev, Nicola
AU  - Kelevedjiev, Emil
AU  - Yurukov, Borislav
TI  - Walk on the Hypercube with Minimum Similarities
JO  - Serdica Journal of Computing
PY  - 2023
SP  - 57
EP  - 70
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJC_2023_16_1_a0/
LA  - en
ID  - SJC_2023_16_1_a0
ER  - 
%0 Journal Article
%A Georgiev, Georgi
%A Yanev, Nicola
%A Kelevedjiev, Emil
%A Yurukov, Borislav
%T Walk on the Hypercube with Minimum Similarities
%J Serdica Journal of Computing
%D 2023
%P 57-70
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJC_2023_16_1_a0/
%G en
%F SJC_2023_16_1_a0
Georgiev, Georgi; Yanev, Nicola; Kelevedjiev, Emil; Yurukov, Borislav. Walk on the Hypercube with Minimum Similarities. Serdica Journal of Computing, Tome 16 (2023) no. 1, pp. 57-70. http://geodesic.mathdoc.fr/item/SJC_2023_16_1_a0/