Метод пошагового конструирования для составления расписания занятий в учебных заведениях

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2008
Автори:	Симоненко, В.П., Симоненко, С.И.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2008
Теми:	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/12003
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Метод пошагового конструирования для составления расписания занятий в учебных заведениях / В.П. Симоненко, С.И. Симоненко // Систем. дослідж. та інформ. технології. — 2008. — № 4. — С. 76-85. — Бібліогр.: 5 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-12003
record_format	dspace
spelling	irk-123456789-120032013-02-13T02:33:00Z Метод пошагового конструирования для составления расписания занятий в учебных заведениях Симоненко, В.П. Симоненко, С.И. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Рассмотрен метод и алгоритм решения задачи составления расписания занятий в учебном заведении со стандартной неделей. Предложенный алгоритм позволяет за конечное число шагов, определяемое количеством занятий и структурой учебной недели, предложить приемлемый вариант расписания. При этом учитываются организационные, методические и психофизиологические требования. Качество расписания, составленного по предложенному алгоритму, в среднем не ниже 0,65%. Розглянуто метод та алгоритм розв’язання задачі складання розкладу занять в учбовому закладі зі стандартним тижнем. Запропонований алгоритм дозволяє за скінченне число кроків, які визначаються кількістю занять та структурою учбового тижня, запропонувати прийнятний варіант розкладу. При цьому враховуються організаційні, методичні і психофізіологічні вимоги. Якість розкладу, складеного за запропонованим алгоритмом, в середньому не нижче 0,65. A method and an algorithm for solving a timetable problem for educational institutions with a standard week are proposed. The algorithm makes it possible to achieve an acceptable version of timetable via a finite number of steps determined by the number of lessons and the educational week structure. Organizational, methodical and psychophysiological requirements are taken into account. The quality of timetables built using the proposed algorithm is not less than 0.65 on average. 2008 Article Метод пошагового конструирования для составления расписания занятий в учебных заведениях / В.П. Симоненко, С.И. Симоненко // Систем. дослідж. та інформ. технології. — 2008. — № 4. — С. 76-85. — Бібліогр.: 5 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/12003 681/324 ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
spellingShingle	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Симоненко, В.П. Симоненко, С.И. Метод пошагового конструирования для составления расписания занятий в учебных заведениях
description	Рассмотрен метод и алгоритм решения задачи составления расписания занятий в учебном заведении со стандартной неделей. Предложенный алгоритм позволяет за конечное число шагов, определяемое количеством занятий и структурой учебной недели, предложить приемлемый вариант расписания. При этом учитываются организационные, методические и психофизиологические требования. Качество расписания, составленного по предложенному алгоритму, в среднем не ниже 0,65%.
format	Article
author	Симоненко, В.П. Симоненко, С.И.
author_facet	Симоненко, В.П. Симоненко, С.И.
author_sort	Симоненко, В.П.
title	Метод пошагового конструирования для составления расписания занятий в учебных заведениях
title_short	Метод пошагового конструирования для составления расписания занятий в учебных заведениях
title_full	Метод пошагового конструирования для составления расписания занятий в учебных заведениях
title_fullStr	Метод пошагового конструирования для составления расписания занятий в учебных заведениях
title_full_unstemmed	Метод пошагового конструирования для составления расписания занятий в учебных заведениях
title_sort	метод пошагового конструирования для составления расписания занятий в учебных заведениях
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2008
topic_facet	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
url	http://dspace.nbuv.gov.ua/handle/123456789/12003
citation_txt	Метод пошагового конструирования для составления расписания занятий в учебных заведениях / В.П. Симоненко, С.И. Симоненко // Систем. дослідж. та інформ. технології. — 2008. — № 4. — С. 76-85. — Бібліогр.: 5 назв. — рос.
work_keys_str_mv	AT simonenkovp metodpošagovogokonstruirovaniâdlâsostavleniâraspisaniâzanâtijvučebnyhzavedeniâh AT simonenkosi metodpošagovogokonstruirovaniâdlâsostavleniâraspisaniâzanâtijvučebnyhzavedeniâh
first_indexed	2025-07-02T14:06:43Z
last_indexed	2025-07-02T14:06:43Z
_version_	1836544377787252736
fulltext	© В.П. Симоненко, С.И. Симоненко, 2008 76 ISSN 1681–6048 System Research & Information Technologies, 2008, № 4 УДК 681/324 МЕТОД ПОШАГОВОГО КОНСТРУИРОВАНИЯ ДЛЯ СОСТАВЛЕНИЯ РАСПИСАНИЯ ЗАНЯТИЙ В УЧЕБНЫХ ЗАВЕДЕНИЯХ В.П. СИМОНЕНКО, С.И. СИМОНЕНКО Рассмотрен метод и алгоритм решения задачи составления расписания занятий в учебном заведении со стандартной неделей. Предложенный алгоритм позво- ляет за конечное число шагов, определяемое количеством занятий и структу- рой учебной недели, предложить приемлемый вариант расписания. При этом учитываются организационные, методические и психофизиологические требо- вания. Качество расписания, составленного по предложенному алгоритму, в среднем не ниже 0,65%. ВВЕДЕНИЕ Одним из основных документов, определяющих функционирование любого учебного заведения, является расписание занятий. Качество составленного расписания влияет не только на усвоение материала учениками, а отсюда и на качество подготовки специалистов, но и на эффективность использова- ния материальных ресурсов учебного заведения. Расписание регламентиру- ет деятельность студентов, преподавателей, обслуживающего персонала. Составление расписания занятий характеризуется множеством требо- ваний, сложностью формализации методов принятия решения и количест- венной оценкой качества полученного варианта расписания. Множество ви- дов расписания определяется принятой в учебном заведении структурой учебного процесса, традициями, количественными и качественными харак- теристиками учебного заведения. Трудности внедрения автоматизированной системы составления расписания связаны не только с решением собственно задачи составления расписания, а и с информационными связями с другими подсистемами автоматизированного управления вузом: приемной комисси- ей, контингентом, кадрами, бухгалтерией, учетом, отчетностью, оператив- ным управлением, материально-техническим снабжением. Все эти подсис- темы информационно взаимосвязаны и влияют на качество решения задачи составления расписания занятий. Для большого вуза невозможно внедрить отдельно систему планирования без внедрения информационно взаимосвя- занных с ней подсистем. Поэтому задачи автоматизированного управления крупным учебным заведением нужно решать комплексно. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ И ВЫБОР МЕТОДА РЕШЕНИЯ В теоретическом плане эта задача является одной из разновидностей задачи назначения и относится к классу NP-сложных [2]. В известных алгоритмах Метод пошагового конструирования для составления расписания занятий … Системні дослідження та інформаційні технології, 2008, № 4 77 составления расписания используются методы теории графов, сетевого пла- нирования, исследования операций. Все алгоритмы можно условно разбить на три группы. 1. Полный или частичный перебор вариантов, их количественный ана- лиз и выбор наилучшего варианта. 2. Моделирование (формализация) действий диспетчера, составляюще- го расписание. 3. Пошаговое конструирование расписания на основании выбранных критериев оптимизации. Алгоритмы первого вида используются для учебных заведений с ма- лым числом групп. Однако для высших учебных заведений с числом групп более 100 их применение неприемлемо из-за экспоненциального роста числа вариантов. Основным недостатком большинства алгоритмов при частичном переборе или основанных на методе ветвей и границ, является изменение уже сделанных назначений и повторение некоторых шагов в случае непри- годности получаемого варианта расписания. Это обусловлено влиянием го- тового расписания групп на составление нового. Здесь требуется коррекция или полное изменение ранее составленных расписаний, что связано с изме- нением базы данных. В случае отсутствия варианта полного размещения заявок по ресурсам может потребоваться полный перебор всех вариантов, что при большой размерности равносильно зацикливанию алгоритма, и де- лает их неприемлемыми ввиду огромных временных затрат. Алгоритмы второго вида относятся к классу эвристических. Они имеют существенный недостаток, заключающийся в невозможности оценить сте- пень опасности назначения занятия на возможность выполнения последую- щих назначений. Наиболее привлекательными являются алгоритмы третьего вида. В предлагаемой статье описывается один из вариантов реализации такого алгоритма. ОПИСАНИЕ АЛГОРИТМА ПОШАГОВОГО КОНСТРУИРОВАНИЯ Основой алгоритма является подход, называемый «методом пошагового конструирования» или «методом направленного поиска» [5]. Цель примене- ния такого подхода — исключить или уменьшить перебор вариантов и обеспечить приемлемое качество составленного расписания. Для этого в предлагаемом алгоритме используются следующие подхо- ды: • Принцип оптимальности Белмана для задач, решение которых мож- но представить в виде связанной цепочки назначений для достижения ко- нечной цели. • Принцип MIN – MAX-ного выбора для поиска места назначения ка- ждого занятия. • Обеспечение конечности составления расписания, т. е. назначение занятия во времени и в пространстве не должно привести к невозможности назначений на последующих шагах работы алгоритма. В.П. Симоненко, С.И. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2008, № 4 78 • Применение понятия «ненадежного состояния системы», которое используется в алгоритме банкира. Под надежным состоянием системы по- нимается состояние, при котором выполнение очередного шага размещения не может привести к конфликту на следующем шаге. Исходная информация для составления расписания в любом учебном заведении: 1. Множество учебных групп, преподавателей, аудиторий, лабораторий. 2. Учебные планы для каждой группы. 3. Индивидуальные характеристики каждого типа занятия, группы, ау- дитории, лаборатории, преподавателя. 4. Перечень требований к расписанию в данном учебном заведении и их характеристика. Требования, которые предъявляются к системам составления расписа- ния занятий, можно разделить на две группы: обязательные и оптимизи- рующие. Выполнение обязательных требований обеспечивает принципи- альную организационную возможность размещения запланированных занятий в имеющихся аудиториях при данных преподавателях и заданной структуре недели. Учет оптимизирующих требований позволяет определить степень предпочтения каждого занятия на любом месте размещения в учеб- ной неделе и выбрать лучшее с точки зрения множества оптимизирующих требований. Наиболее важные обязательные требования: 1. Выполнение учебного плана занятий. 2. Соответствие возможностей аудиторий численности учебных групп. 3. Исключение «накладок» в занятиях у преподавателей, групп, ауди- торий, лабораторий. 4. Соответствие вместимости аудиторий, лабораторий численности на- значенных в эти аудитории групп. 5. Возможность резервирования (блокирования) определенных вре- менных интервалов у преподавателей, аудиторий, лабораторий (профилак- тика). Выполнение обязательных требований обеспечивает организационную возможность проведения занятий. Оптимизирующие требования: 1. Учет пожеланий преподавателей. 2. Предварительное резервирование аудиторий. 3. Равномерная загрузка дней недели. 4. Равномерное распределение различных форм занятий в неделю. 5. Равномерное распределение занятий по одной дисциплине в неделю. 6. Равномерное распределение занятий с учетом сложности предметов. 7. Уменьшение «окон» у преподавателей и групп. Сложность решения задачи составления расписания определяется со- вокупностью и взаимосвязью дисциплин, входящих в учебный план, струк- турой учебной недели, перечнем требований к системе планирования. Исходной информацией для решения задачи по предлагаемому алго- ритму является совокупность заявок и их индивидуальные характеристики, Метод пошагового конструирования для составления расписания занятий … Системні дослідження та інформаційні технології, 2008, № 4 79 позволяющие определить степень предпочтения каждой заявки (в диопазо- не от 0 до 1) на каждый временной интервал недели. Базовая информация для составления расписания — учебный план для группы (класса), где указаны название предмета, тип занятия, число часов в неделю, преподаватель и необходимая аудитория (рис. 1). Кроме этого для составления расписания необходимо знать предвари- тельную загрузку преподавателей, аудиторий, лабораторий. На рис. 2 пока- зана предварительная информация о загрузке преподавателей перед состав- лением расписания. Процесс составления расписания разделен на два шага: распределение занятий во времени (по дням и урокам) без назначения аудиторий общего пользования и аудиторий с учетом длительности переходов учащихся. Од- нако при выполнении первого шага учитываются возможности аудиторного фонда учебного заведения. Общее количество назначенных занятий в любой временной интервал не должно превышать количества аудиторий опреде- ленной вместимости и вида. Выполнение этого требования позволяет полу- УЧЕБНЫЙ ПЛАН КЛАССА 9-А Рис. 1. Учебный план одного класса средней школы Рис.2. Предварительная загрузка преподавателей В.П. Симоненко, С.И. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2008, № 4 80 чить конечное решение при последующем назначениии аудиторий. Предла- гаемый алгоритм назначения занятий во временных координатах недели со- держит следующие шаги. 1. Формирование специальной матрицы выбора (МВ). 2. Анализ МВ, диагностика конфликтных ситуаций и выработка ре- комендаций по коррекции исходной информации. 3. Выполнение обязательных назначений. 4. Выбор занятия для размещения. 5. Выбор дня недели и номера урока для занятия. 6. Коррекция МВ и переход к п.2 до полного размещения всех заня- тий. На первом шаге используется табличный метод управления и формиру- ется двумерная булева МВ. В ней отражается принципиальная возможность каждого запланированного занятия в каждом временном интервале (дне и уроке). При этом учитывается текущая загрузка групп, преподавателей, ау- диторий или лабораторий. Структура МВ и ее использование принципиаль- но исключают появление «накладок» или конфликтных ситуаций в конеч- ном расписании. Рассмотрим формирование строки МВ на следующем примере (рис. 3). Для определения места возможного размещения лекционного занятия L необходимо учитывать текущую загрузку преподавателя P, аудитории A и группы G. Обозначим «1» физическую возможность проведения занятия и «0» — невозможность. Тогда для P, A, G после анализа исходной информа- ции будут сформированы следующие векторы а, б, в. В результате выполнения логического умножения векторов P, A, G по- лучаем результирующий вектор L, где и отображаются те временные интер- валы (дни и уроки), в которые возможно размещение дисциплины L. Опи- санная операция выполняется для всех дисциплин учебного плана группы, для которой составляется расписание. В результате получаем МВ, показан- ную на рис. 4. На втором шаге выполняется анализ МВ с точки зрения ее корректно- сти. В случае невозможности размещения запланированных занятий в сетке недели производится детальный анализ конфликта, определяется его причи- Рис. 3. Формирование строки МВ Метод пошагового конструирования для составления расписания занятий … Системні дослідження та інформаційні технології, 2008, № 4 81 на и в автоматическом или интерактивном режиме производится коррекция исходной информации. Предложенная форма МВ позволяет выделить на- значения, которые являются обязательными, т.е. имеющими единственное место размещения. При этом размерность решения задачи уменьшается, а МВ корректируется [4]. Одним из недостатков алгоритмов, использующих метод ветвей и границ и на основании этого пошагового составления распи- сания, является обнаружение неверно сделанного назначения, т.е. назна- чения, приводящего к конфликту, только после выполнения нескольких ша- гов. В предлагаемом алгоритме на стадии предварительного анализа исход- ной информации возможно исключение заведомо конфликтных назначений. Для их выделения предлагается эквивалентное преобразование МВ, анализ новой МВ', определение конфликтных зон. Преобразование выполняется на основе модифицированного алгоритма Мальгранжа [1], а анализ — на раз- работанных решающих правилах с использованием теорем Фробениуса- Кенига и Минка [3], относящихся к вычислению перманента (0,1) матриц. На рис. 5–7 показаны примеры результатов преобразования МВ и ее кор- рекции для некоторых случаев, на рис. 5 — вариант, когда система состав- ления расписания имеет единственное решение, на рис. 6, 7 — различные варианты определения конфликтных зон и их коррекции. Рис. 4. Выбор дисциплины для размещения Рис. 5. Вариант единственного решения составления расписания Исходная матрица Матрица после преобразования Матрица после коррекции В.П. Симоненко, С.И. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2008, № 4 82 На третьем шаге выбирается дисциплина для размещения. Для этого используется принцип мини-максного выбора. Т.е. выбирается дисциплина, находящаяся в худшем положении по отношению к другим. Для каждой дисциплины i вычисляется коэффициент выбора iKv и в дальнейшем вы- бирается дисциплина, имеющая минимальное значение iKv (определяется как сумма единиц или возможных мест размещения анализируемой дисци- плины i в сетке недели). Здесь используется сформированная и скорректи- рованная на предыдущих шагах МВ'. Данная стратегия уменьшает возмож- ность перехода системы в ненадежное состояние. Четвертый шаг предназначен для определения временного интервала размещения выбранной на предыдущем шаге дисциплины. Для каждого возможного места размещения в сетке недели (дня и урока t ) дисциплины i вычисляется коэффициент претендования tKp, , который является ком- плексным коэффициентом, учитывающим выполнение множества опти- мизирующих требований для каждого возможного места размещения вы- Рис. 6. Единственная конфликтная зона Рис. 7. Множество конфликтных зон Метод пошагового конструирования для составления расписания занятий … Системні дослідження та інформаційні технології, 2008, № 4 83 бранной дисциплины. При вычислении tKp, , учитывается текущее состоя- ние системы планирования, т.е. расположение уже назначенных занятий и весовые коэффициенты каждого оптимизирующего требования. Использо- вание весовых коэффициентов позволяет адаптировать, настроить систему к учебному заведению. tKp, вычисляется из выражения ( )∑∏ == ×××= N y M x tRyKytRxtKktKp 11 ,,,, , Tt …1= , где tKk , — коэффициент безопасности назначения выбранного занятия L во временной интервал t (при его вычислении учитывается степень претен- дования других дисциплин на размещение в анализируемом интервале t ); tRx, — степень выполнения обязательного требования х во временной интервал t (может принимать значения 0 или 1); tRy, — степень выполнения оптимизирующего требования y во вре- менной интервал t (может принимать значения от 0 до 1); Ky — весовой коэффициент Ry требования (значения определяются методом экспертных оценок или подбираются экспериментальным путем во время эксплуатации системы). В результате вычисления коэффициентов tKp, и временного интервала t с максимальным значением коэффициента tKp, выполняется назначение занятия L в этот временной интервал. При этом необходимо скорректиро- вать загрузку преподавателей, аудиторий или лабораторий и записать соот- ветствующую информацию в расписание группы. Кроме этого выполняется коррекция МВ, т.е. «зануляется» строка распределенной дисциплины и столбец, соответствующий временному интервалу, в который эта дисцип- лина распределена. После этих операций выполняется переход к п. 2 алгоритма и описан- ные выше шаги повторяются до полного составления расписания. На рис. 8 показан пример выполнения одного шага размещения, где временной ин- тервал выбирается с максимальным значением Kk . После выполнения описанных действий для всех дисциплин учебного плана получаем окончательное расписание (рис. 9). Рис. 8. Пример выбора времени проведения занятия В.П. Симоненко, С.И. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2008, № 4 84 ОПРЕДЕЛЕНИЕ ВРЕМЕННОЙ СЛОЖНОСТИ АЛГОРИТМА Временная сложность составления расписания по предлагаемому алгоритму может быть определена совокупностью временных сложностей отдельных фаз. Естественно, что в случае, если конечного решения нет, то оценка вре- менной сложности неверна, так как система выполняет операции по диагно- стике конфликта и формированию рекомендаций по его исключению. Опре- делим временную сложность каждого шага. Временная сложность процедуры определения конфликтных назначе- ний равна )](log2[ nnO , а коррекции МВ — ]5,0[ eO ∗ . Тогда общая вре- менная сложность выделения конфликтных назначений и коррекции МВ равна ]5,0)(log2[ ennO ∗+ . Временная сложность процедуры выбора дисциплины для размещения равна ][ 2nO , а временная сложность процедуры определения временного интервала для размещения занятия в худшем случае равна ][ 2 PNnO ∗+ (где n — размерность МВ на текущем шаге размещения занятия; N — количество оптимизирующих требований; P — общее количество заня- тий в учебной неделе). Временная сложность одной фазы размещения одно- го занятия равна +=∗+++∗+ )(log2[]5,0)(log2[ 22 nnOPNnnennO ]2 2 PNn ∗++ . Для определения общего количества фаз следует учитывать, что оно равно количеству распределяемых занятий и соответствует размер- ности матрицы выбора. Кроме того, размерность МВ уменьшается по мере распределения занятий. Тогда общую временную сложность предлагаемого эвристического алгоритма составления расписания можно определить из формулы ( )( ) ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ×++×∑ = 1 22Log2 Dn PNnnnO . Рис. 9. Вариант расписания для одного класса Расписание для класса 9–А РАСПИСАНИЕ ДЛЯ ПОДГРУППЫ НОМЕР 1 Метод пошагового конструирования для составления расписания занятий … Системні дослідження та інформаційні технології, 2008, № 4 85 ВЫВОДЫ 1. Выполнение предварительного анализа исходной информации и вы- работка стратегии ее решения позволяют: а) определить принципиальную возможность решения; б) локализовать причину конфликта; в) определить обязательные назначения, а также г) назначения, приводящие к конфликту; д) уменьшить размерность решения задачи при выполнении пунктов а) и б). 2. Использование концепции надежного состояния системы планиро- вания и вычисление коэффициентов Kvi, Kk, t в соответствии с этой концеп- цией, а также выполнение анализа исходной информации перед выполнени- ем очередного шага и исключение конфликтных назначений практически позволяет избежать повторения уже выполненных шагов. 3. Примерное время составления расписания для одной учебной груп- пы с 36-ю уроками в неделю требует до 0,2-й секунды машинного времени в зависимости от используемого компьютера. ЛИТЕРАТУРА 1. Берж К. Теория графов и ее применение. — М.: Изд. иностр. лит., 1962. — 320 с. 2. Гери М.Р., Джонсон Д.С. Вычислительные машины и труднорешаемые зада- чи. — М: Мир, 1982. — 416 с. 3. Липски В. Комбинаторика для программистов. — М.: Мир, 1988. — 213 с. 4. Самофалов К.Г., Луцкий Г.М., Симоненко В.П. Метод предварительного анали- за исходной информации и выработки стратегии решения задачи назначе- ния в распределенной вычислительной среде // Электронное моделирова- ние. —1995. — №4. — С. 36–40. 5. Симоненко В.П. Метод пошагового конструирования решения при распределе- нии задач в параллельных вычислительных системах // Вісн. національного технічн. ун-ту України «КПІ» Сер. інформатика, управління та обчислю- вальна техніка. — 2000. — № 33. — С. 15–21. Поступила 16.11.2006

Метод пошагового конструирования для составления расписания занятий в учебных заведениях

Репозитарії

Схожі ресурси