33. Теорема С. Джонсона и алгоритм оптимального расписания выполнения работ в “задаче о двух станках”.
К списку вопросов
Расписанием можно назвать документ, содержащий сведения: о кол-ве и номенклатуре выполняемых работ, включая их этапы, о моментах начала и окончания каждой работы , о месте и технических средствах выполнения каждой работы, о материальных затратах на проиводимые работы и т.д.
Расписание можно задавать различными способами, среди которых более наглядными являются геометрический, основанный на использовании Гант-карты: каждой работе ставится в соответствии отрезок определенной длины на временую ось, при известном начале отсчета времени (t=0) взаимное расположение отрезков дает всю необходимую информацию о расписании работ.
Теория расписания исторически возникла из задачи о двух станках, выполняющих последовательно N работ:
С помощью Гантт-карт можно наглядно представить работу на двух типах оборудования.
N - видов работ.
1 или 2 в индексе работы указывает на каком станке она выполняется:
Сформулируем задачу о двух станках.
Пусть имеется N видов работ, каждая из которых выполняется сначала на станке 1, а затем на станке 2. В начальный момент времени t=0 первая по установленной очереди работа попадает на первый станок и занимает его некоторое время ?11, после чего переходит на 2-й станок, где её выполнение заканчивается за время . Этот цикл повторяется для всех остальных работ, проводимых по мере освобождения станков при соблюдении следующих условий:
1. на каждом станке проводится не более одной работы одновременно;
2. каждая работа проводится без прерываний и её переход на 2-й станок возможен лишь после того, как она полностью завершиться на 1-ом станке;
3. 1-й станок не должен простаивать.
Требуется найти такой порядок проведения работ (расписание), который обеспечивает минимум полного времени занятости Тс рассматриваемой двухстаночной системы.
Для сформулированных условий имеется теорема Т.С. Джонсона (достаточное условие миним. работы двустаночной системы)
При возможном произвольном выборе имеющихся N работ порядок их выполнения, обеспечивающий min{Тс}, должен удовлетворять требованиям:
Эта теорема позволяет резко сократить кол-во требуемых вариантов
К списку вопросов
