Из-за высокой вычислительной трудоемкости, а также возможности распараллеливания вычислительных процессов, присущей алгоритмам дискретной оптимизации (ДО), разработка параллельных алгоритмов для решения задач ДО представляет значительный интерес. Параллельные вычислительные системы обладают возможностями параллельного использования большого числа процессоров для обработки информации. Разумное использование вычислительного потенциала посредством распараллеливания вычислительного процесса существенно ускоряет решение практически важных задач ДО большой размерности. Современные достижения параллельных ме- тодов комбинаторной оптимизации описаны в [1]. Декомпозиционные алгоритмы ДО являются первоочередными кандидатами для параллелизации. Для решения задач ДО с помощью декомпозиционных методов представляют интерес системы с распределенной памятью. Параллельное программное обеспечение (ПО) для этих систем использует явную декомпозицию решаемой задачи на подзадачи и назначение их процессорам, а также быструю коммуникационную сеть, обеспечивающую синхронный обмен данными между процессорами. Наиболее типичной архитектурой является Беовульф кластер, важные свойства которого: однородность, коммуникационная сеть типа «все-со-всеми», отсутствие общей памяти и отсутствие глобальных часов для синхронизации вычислений.