Приближенный алгоритм решения задачи трех станков

Доказывается $NP$-полнота в сильном смысле для одной из многочисленных подзадач проблемы трех станков (машин) [1]. На основе доказательства предлагается приближенный метод решения с полиномиальным временем работы для общего случая задачи Беллмана–Джонсона $3\times n$.