Системы с многофазным обслуживанием.

Рассмотрим теперь следующую задачу: пусть необходимо выполнить п работ, каждая из которых выполняется последовательно в пунктах А и В. Обозначим через В і время выполнения і-й

(г = 1 , ...,п) работы в пунктах А и В соответственно.

Выполнение очередной работы в пункте В связано с возможным ожиданием завершения обслуживания предыдущей работы. Джонсоном показано, что при доступности всех работ в каждый такт времени оптимальное расписание таково, что

Таблица 2.1

работа г предшествует работе j, если min(Ai,Bj) < min(Aj,Bi).

Рассмотрим пример. Пусть имеются шесть работ, которые первоначально выполняются в порядке, указанном в табл. 2.1. В таблице содержатся также длительности выполнения данных работ на пунктах А и В.

Построив диаграмму совмещения работ (рис. 2.1) с учётом возможных простоев, связанных с ожиданием освобождения пункта В, находим, что общее время Т выполнения всех работ в порядке, представленном таблицей, равно 35.

Рис. 2.1. Диаграмма совмещения потоков работ

Таблица 2.2

Рис. 2.2. Оптимальная диаграмма совмещения потоков работ

Производя сортировку работ в соответствии с алгоритмом Джонсона, находим оптимальный порядок выполнения работ (рис. 2.2, табл. 2.2). Для данного упорядочения работ Т = 27.

Задача для упорядочения работ на трёх пунктах сводится, при определённых условиях, к задаче для двух пунктов путем объединения соответствующих работ, выполняемые в пунктах А и В или пунктах В и С: соответствующие длительности работ при этом складываются. Класс задач, к которым применим алгоритм Джонсона, таким образом, ограничен. В случаях, когда п > 3 для решения используют, как правило, эвристические или приближенные методы.

Один из таких подходов для многостадийного циклического выполнения комплекса работ приведён ниже.

2.1.2.