Метод приоритетов для задач разработки расписаний

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

4. Некоторые области применения результатов ТР в  информатике и  вычислительной технике

 

• организация больших информационных систем –  создание аппаратно-программных комплексов параллельной обработки данных (массово-параллельных систем МРР);
• усовершенствование микроархитектуры процессоров (одна из особенностей процессора Р6 – наличие блока диспетчера\обработки, который планирует расписание обработки субъектов микроопераций с учетом их взаимозависимости по данным и наличным ресурсам);
• разработка ПО планирования коллективной работы (управления проектами).

 
 
 
 
 
 
 
 
 
 
 
 
 

Пример  конкретного  расписания  экзаменов факультета ИСТАС

 

  У нас  имеется:

  -четыре дисциплины: электротехника(э), физика(ф), мат.анализ(м), компьютерная графика(г)

  -четыре свободные даты

Требуется составить  расписание, таким образом чтобы  не случилось пересечений.

1)А=n! =1х2х3х4=24

А-число вариантов  перестановок дисциплин 

n-количество дисциплин 

2) Граф вариантов  перестановок 

 
 

Для того, чтобы избежать пересечений необходимо выполнения одного из условий: 

1)Группы сдают  экзамены в разные дни 

2)Группы сдают  экзамен в один и тот же  день, но по разным дисциплинам.  

Для первого  условия подходит абсолютно любой  из нашего графа.

Для соблюдения второго условия необходим определённый алгоритм выбора пути(расписания): 

1.Выбираем для  одной из групп любой путь 

2.Выбираем следующий  путь для другой группы 

3.Ищем пересечения:  if пересечений нет, => расписание готово,  else повторяем пункт 2 

Расписание (вариант  первый). Группы сдают экзамены в  одни и те же дни. 

 

Пересечений нет=>расписание готово. 
 
 
 
 
 

Расписание (второй вариант). Группы сдают экзамены в  разные дни. 

 

Пересечений нет => расписание готово. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   Содержание.

1.   Э.Г.Коффман «Теория расписаний и вычислительные машины» - Наука,1984;

2. www.bibliofond.ru

3. www.wikipedia.ru

4. Александров П.С. Ведение в теорию множеств и теорию функций.-М.:Наука,1997 г.