Предлагаются эффективные приближенные методы решения Job-Shop-Problem. На основе установленных свойств допустимых и оптимальных расписаний на первых шагах работы алгоритма устанавливается факт совместности исходной системы ограничений, вычисляются нижние границы критерия эффективности в оптимальном решении. Алгоритм приближенного решения задачи строится на основе построения на каждом шаге решения допустимого расписания выполнения работ на наиболее напряженной машине и корректировки наиболее ранних и допустимых наиболее поздних сроков начала выполнения каждой операции на других машинах, сроки выполнения на которых еще не назначены. Ключевые слова: Job-Shop-Problem, оценки оптимального решения, приближенные решения, граничные сроки начала выполнения операций, свойства допустимых и оптимальных расписаний
