Современные информационные технологии /2. Вычислительная техника и программирование

 

К.ф.-м.н. Хачумов М.В.

Институт системного анализа Российской академии наук, Россия

Задача циклического обслуживания набора двухстадийных работ

 

         В известной задаче Джонсона рассматривается обслуживание партии заявок (работ, изделий) на двух приборах (станках, процессорах) [1]. Пусть, например, необходимо выполнить  работ, каждая из которых проходит последовательно две фазы обслуживания на процессорах  и  соответственно (рисунок 1).

 

Рисунок 1 − Двухфазная обслуживающая система

Обозначим через – время выполнения -ой  работы на процессорах  и  соответственно. По Джонсону оптимальное расписание таково, что работа  предшествует работе j, если  [1].

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

 

Таблица 1−Исходный порядок выполнения работ

Фазы и время обслуживания

№ работы и порядок ее обслуживания

1

2

3

4

5

6

2

6

8

4

4

2

5

1

2

4

7

4

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

Таблица 2− Оптимальный порядок выполнения работ

Фазы и время обслуживания

№ работы и порядок ее обслуживания

6

1

4

5

3

2

2

2

4

4

8

6

4

5

4

7

2

1

Расписание оптимального выполнения работ по Джонсону представлено на рисунке 2. Фактически диаграмма представляет собой систему их двух связанных последовательностей работ на процессорах  и .

         Каждая последовательность работ разбита на такты (фазы) в соответствии с указанными в таблицах длительностями. В общем случае возможны простои процессора  и возникновение очередей во втором слое.

Рисунок 2 − Диаграмма выполнения работ

Для оптимального упорядочения работ по Джонсону T = 27. 

         Рассмотрим задачу многократного (циклического) выполнения партий изделий на двух станках при неизменном порядке обслуживания в партии. Для каждого процессора выпишем порядковые номера закрепленных за ними фаз в соответствии с рисунком 2. Если  и - две разные фазы закрепления процессора, то величину  назовем сдвигом фазы. Таким образом, для каждого процессора i-го типа можно выписать множество сдвигов фаз , а всему варианту диаграммы поставить в соответствие множество . Введем далее множество  такое, что  где , . Множество сдвигов  определяет запрещенные сдвиги между фазами обработки двух соседних партий работ в расписании, а  - разрешенные сдвиги. Из построений на рисунке 2 следует, что ,   поэтому =26. Определим среднее время  одного цикла многократной обработки партии в тактах. Обозначим  тогда , причем первый результат будет получен через  тактов, а все последующие  через 26.

Проведенные рассуждения могут быть распространены на случай когда число фаз больше двух и обобщены на произвольные виды многократно выполняемых партий [2]. Работа выполнена при поддержке проекта РФФИ № 13-07-12162 офи_м «Исследование и разработка методов и алгоритмов синтеза медицинских технологических процессов на основе прецедентной информации».

Литература:

1.     Конвей Р.В. Теория расписаний: Пер. с англ./Конвей Р.В., Максвелл В.Л., Миллер Л.В – М.: Наука, Гл. ред. физ.-мат.лит., 1975. –359 с.

2.     Хачумов М.В. Оптимизация медицинских технологических процессов с использованием методов искусственного интеллекта. – В сб. трудов XX Международной научн. Конференции «Математические методы в технике и технологиях (ММТТ-20) (Ярославль, 28-31 мая, 2007). – Ярославль: Изд-во ЯГТУ, Т.9, 2007, с.81-84.