Walk on the Hypercube with Minimum Similarities

Authors

  • Georgi Georgiev Faculty of Mathematics and Informatics, Sofia University"St. Kliment Ohridski", Bulgaria
  • Nicola Yanev Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Bulgaria
  • Emil Kelevedjiev Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Bulgaria
  • Borislav Yurukov Department of Informatics, South-West University "Neofit Rilski", Blagoevgrad, Bulgaria

DOI:

https://doi.org/10.55630/sjc.2022.16.57-70

Keywords:

Scheduling, Travelling Salesman Problem, Transportation Problem, Integer Programming

Abstract

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.

Downloads

Published

2023-03-02

Issue

Section

Articles