Tabu search employs memory structures to prevent premature convergence and to better explore the search space. The design of the tabu list is often viewed as a technical detail rather than a crucial component. Classical tabu search stores entire solutions or moves explicitly. In the case of large, combinatorial problems, this approach proves slow and inefficient. Exact storage requires costly comparison operations, large storage requirements, and disregards similarities between solutions. The result is an algorithm that can still be limited, despite keeping track of solutions, since it may cycle between similar solutions despite being different at the representation level. This is usually due to solution encodings being simplified to aid search, instead of representations of full solutions — which are usually derived by a decoding scheme, often with semi-active scheduling.

Our paper proposes an alternative tabu list by utilizing attributes as well as full solutions while keeping memory usage to a minimum. These attributes are a generalization of each encoding without running a full simulation. This is enabled by the use of Bloom filters. Attribute-based Bloom filters are built from a list of attributes extracted from each solution. These attributes can be domain-driven. Problem-aware attributes include permutation fragments, assignment patterns, temporal relations, or aggregated features from processing times, setup times, due dates, start times, transfer times, etc. These attributes relate to decodings by identifying patterns not apparent in permutations themselves. Each attribute is mapped onto its own Bloom filter, forming a series of compact multi-filters with constant-time membership queries and strictly bounded memory usage.

This attribute-based approach shifts the role of tabu memory from exact, syntax-based repetition avoidance to a more general, semantic similarity. By marking attributes alongside complete solutions, the search is discouraged from exploring similar structural regions, even when their representations differ syntactically.

However, this level of generalization remains adjustable through hashing policies and attribute selection.

A practical advantage is a broader range of filtered solutions that likely provide similar results, reducing the number of costly simulation and evaluation calls — and the ability to merge multiple, concurrently produced tabu lists efficiently. These abilities enable us to utilize tabu search in multi-threaded and population-based search algorithms as local search without expensive synchronization operations.

The method is evaluated on permutation-based scheduling problems with complex constraints and simulation-driven objective functions. The results indicate that Attribute-based Bloom filters provide more stable search and improved diversification — compared to classical tabu lists or simple genetic algorithms — while incurring negligible computational overhead. These findings suggest that treating tabu memory as an attribute-level component — rather than just a solution-level cache — can offer practical benefits in modern, large-scale optimization settings.