Journals Conferences Monographies Textbooks Regulatorys Event GQW
Submit manuscript
Home / Journals / Vestnik of Astrakhan State Technical University. Series: Management, computer science and informatics / Volume 2016 Issue 3 / GENERALIZED ALGORITHM OF SCHEDULING IN THE UNIVERSITY TAKING INTO ACCOUNT THE NEW REQUIREMENTS OF THE FEDERAL STATE EDUCATIONAL STANDARDS
GENERALIZED ALGORITHM OF SCHEDULING IN THE UNIVERSITY TAKING INTO ACCOUNT THE NEW REQUIREMENTS OF THE FEDERAL STATE EDUCATIONAL STANDARDS
Submit manuscript
To cite
Citations:

GENERALIZED ALGORITHM OF SCHEDULING IN THE UNIVERSITY TAKING INTO ACCOUNT THE NEW REQUIREMENTS OF THE FEDERAL STATE EDUCATIONAL STANDARDS
Khasukhadzhiev Apti Said-Akhmadovich 1
Sibikina Irina Vyacheslavovna 2
Authors:
1.  Astrakhan State Technical University

2.  Astrakhan State Technical University (Candidate of Technical Sciences, Assistant Professor; Assistant Professor of the Department of Information Security )

Type:
Article
Pages:
from 78 to 86
Status:
Published
Received:
05.07.2016
Accepted:
28.02.2020
Published:
25.07.2016
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 519.854.2
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
scheduling, management, requirements, algorithm
Abstract and keywords
Abstract (English):
The paper considers the process of scheduling in higher educational institutions and presents the classification of the types of schedules and the requirements in their drafting. The advantages and disadvantages of the modern approaches to automation of scheduling are analyzed, the data about the used mathematical models and algorithms are resented. The initial data necessary for scheduling the training classes are determined. A lot of indicators of the estimation of the schedule quality are specified, the ways of reduction of the criteria for simplification of the procedure of choosing the appropriate schedule are illustrated. The algorithm of task solution on scheduling is developed, the block-scheme of the algorithm generalizing different scientific studies on the topic is presented. It is stated that scheduling is not a single-step act, as during the training process the schedule can require to be specified to provide the replacement of the teachers when they are dismissed, absent due to the business trip or sick leave, i. e. the development of the data base for automatic generation of the schedules still remains an essential task.

Keywords:
scheduling, management, requirements, algorithm
Text
Введение Внедрение кредитной технологии обучения требует от высших учебных заведений дальнейшего укрепления учебно-методической, материально-технической и научной базы. Задача составления расписания должна учитывать новые требования по организации учебного процесса. Это скажется на количестве показателей и ограничений при реализации алгоритмов выбора наилучшего расписания занятий. Задача автоматизации управления учебным процессом в высшем учебном заведении характеризуется [1]: - большим объемом разнородной обновляемой информации из различных структурных подразделений вуза, таких как учебный отдел, деканаты, кафедры, отделы АСУ и информационной безопасности; - сложностью формализации и идентификации параметров [2] и ограничений составляемого расписания, степень и качество учета которых полностью зависят от опыта и квалификации ответственного работника учебно-методического управления; - конфликтом интересов основных участников учебного процесса: студентов и преподавателей, кафедр - как владельцев специализированного оборудования и аудиторий, что налагает ограничения на свободу их использования в расписании; - трудоёмкостью адаптации универсальных алгоритмов составления расписания к нуждам конкретного учебного заведения, особенно с учетом новых условий работы вузов. Ключевыми направлениями модернизации новых возможностей реализации образовательных программ являются: - электронное обучение; - дистанционные образовательные технологии; - создание кафедр на производстве; - создание условий для обучения лиц с ограниченными возможностями здоровья и многое другое [3, 4]. Все это напрямую связано с планированием нагрузки преподавателей, которым потребуется больше свободного времени на внеаудиторную работу по подготовке новых курсов и их адаптации к новым требованиям на основе компетентностного подхода, подготовку научных статей, ведение документации и обновление учебно-методических комплексов каждые 5 лет, дистанционное общение со студентами и т. д. Следовательно, процесс формирования расписания также должен быть адаптирован к новым требованиям, а качество составленного расписания должно быть напрямую связано с эффективностью учебного и воспитательного процесса в вузах. Анализ задачи теории расписания в современных условиях Первые опубликованные исследования на тему автоматизации при составлении расписаний занятий появились еще в ХХ в. Математической основой таких работ является теория расписаний - раздел исследования операций, в котором строятся и исследуются математические модели календарного планирования. Задачи составления расписания возникают в разных сферах деятельности: - производство (упорядочение технологических операций по исполнителям и по времени); - транспорт; - образование (организация учебного процесса). Задаче о составлении оптимального расписания в той или иной области посвящено довольно большое количество работ [1, 5-24], что говорит о ее сложности и практической значимости. Подобные задачи связаны с упорядочением некоторых работ в зависимости от количества исполнителей или времени. Одновременно необходимо учитывать ограничения на последовательность выполнения работ, ограничения, связанные с исполнителями, и т. п. Цель решения таких задач - это построение допустимых расписаний при соблюдении всех ограничений или нахождение оптимального допустимого расписания по тому или иному критерию оптимальности (понятие оптимальности здесь заменяется понятием допустимости, удовлетворительности, рациональности), что является ещё более сложной задачей. Задача о составлении расписания в вузе является задачей многокритериальной оптимизации, т. к. необходимо учитывать достаточно большое количество критериев. Как правило, критериям назначается степень важности, оказывающая существенное влияние как на процесс, так и на качество составляемого расписания. Решение задач теории расписаний усложняется тем фактом, что большинство из них являются NP-трудными [4], и алгоритмы их решения, реализованные на ЭВМ, должны быть адаптированы для получения приемлемого варианта за предельно допустимое время. Отметим, что задача составления расписания зависит от других смежных задач, которые необходимо решать при организации учебного процесса, например от задачи составления учебной нагрузки, т. к. варианты ее распределения могут по-разному влиять на качество итогового расписания. Представим классификацию типов расписаний, которые генерируются в ходе реализации образовательных программ. Видами учебных расписаний для студентов являются: - расписание теоретических занятий (лекционных); - расписание практических занятий (семинары, практики); - расписание лабораторных занятий; - расписание промежуточной аттестации (экзаменационной сессии); - расписание ГИА (государственной итоговой аттестации); - расписание ГАК (государственной аттестационной комиссии); - расписание ликвидации академической задолженности; - расписание консультаций студентов; - расписание дистанционного общения со студентами, имеющими ограничения по здоровью. Сбор входных данных Исходными данными для составления расписания учебных занятий являются: - компетентностно-ориентированный учебный план специальности; - график учебного процесса; - тарификационная нагрузка преподавателей на учебный год; - виды учебных занятий (лекции, практические занятия, лабораторные работы); - сведения об имеющемся аудиторном фонде и его оборудовании; - данные о количестве студентов в учебных группах (подгруппах); - распределение групп для практических занятий между преподавателями; - мотивированные пожелания преподавателей. Таким образом, в качестве исходной информации при составлении расписания учебных занятий выступают: 1.Множество дисциплин изучения S (S1, …, SNs). Будем считать, что дисциплины S1 и S2, ассоциированные с одним и тем же предметом, например предметом «Методы оптимизации», различаются по признаку «Тип занятия»: S1 - «Методы оптимизации - лекция»; S2 - «Методы оптимизации - лабораторная». 2. Множество учебных групп G (G1, …, GNg). 3. Множество преподавателей T (T1, …, TNt). 4. Множество аудиторий, имеющихся в распоряжении A (A1, …, ANa). 5. Множество временных интервалов (пар) P (P1, …, PNp). 6. Множество требований D (D1, …, DNd). В вышеперечисленных множествах приняты следующие обозначения: NS - число дисциплин обучения; NG - число учебных групп; NT - число преподавателей; NA - число аудиторий; NP - число пар в течение семестра, причём пара представима в формате неделя.день.пара и их количество строго оговорено с учетом режима работы учреждения (пятидневка или шестидневка и др.) и определяется произведением числа дней в неделе (5 или 6), пар в течение дня (максимум 6) и количеством типов недель при формировании расписания (2 - четная и нечетная); ND - множество требований. Такие элементы расписания, как ПРЕДМЕТ, АУДИТОРИЯ И ПРЕПОДАВАТЕЛЬ не равноценны по отношению друг к другу по разным причинам и могут быть проранжированы. Например, в обеспечение требований новых федеральных государственных образовательных стандартов (ФГОС) доля работников из числа руководителей и работников организаций, деятельность которых связана с направленностью (профилем) образовательной программы, должна составлять не менее 10 %. Для них и сотрудников, совмещающих административные или другие должности, должны быть обеспечены «льготные» условия расписания в первую очередь. При распределении нагрузки, а следовательно, и составлении расписания (учитываем, что разрабатываемое информационное обеспечение специалисты в вузах, как правило, стараются интегрировать друг с другом) необходимо учитывать, чтобы кадровое обеспечение (доля ставки имеющих образование, соответствующее профилю преподаваемой дисциплины) было не менее 70 %. Это означает, что актуальна и задача оценки качества расписания по построенной модели нагрузки преподавателей кафедры с учетом новых требований ФГОС. Аудитории также могут различаться в зависимости от их соответствия: - правилам и нормам безопасности; - нормативам площадей; - возможностям индивидуального доступа к сети Интернет; - наличию свободного и лицензионного программного обеспечения; - наличию в аудитории специальных технических средств (электронные замки для учета посещаемости, видеокамеры для осуществления видеозаписи при защите выпускной квалификационной работы, проекторы, интерактивные доски; специальное оборудование для учащихся с ограниченными возможностями). Требования, предъявляемые к расписанию учебных занятий К расписанию предъявляется множество требований. Требования при составлении расписания также ранжируются и делятся на основные и второстепенные. К основным требованиям можно отнести следующие: 1. Отсутствие накладок. 2. Соответствие количества мест в аудитории количеству человек в группе. 3. Отсутствие «окон». 4. Соответствие аудитории типу занятия. 5. Обязательное проведение полного объёма занятий по учебному плану. 6. Ограничение на объём ежедневных занятий. К второстепенным требованиям отнесём следующие: 1. Равномерность нагрузки студентов в течение всего семестра и конкретного учебного дня. 2. Минимизация переходов между аудиториями или корпусами. 3. Избыточность количества мест в аудитории по отношению к количеству учащихся. 4. Компактность нагрузки преподавателей. Для сравнения вариантов расписания с точки зрения компактности (т. е. количества свободных дней для подготовки к аудиторным занятиям и выполнению научной, методической и организационной работы) предлагается следующая формула: , где - суммарное количество дней с аудиторными занятиями; - суммарное количество пар в течение недели. 5. Периодичность расписания и т. д. Обобщённая классификация требований к расписанию в вузе приведена на рис. 1. Рис. 1. Классификация требований при составлении расписания Общие этапы процесса обработки данных для формирования расписания приведены на рис. 2. Рис. 2. Диаграмма потоков данных Требования к составлению расписания экзаменационных сессий и показатели качества при составлении расписания Кроме требований, предъявляемых к расписанию учебных занятий, существует ряд требований к составлению расписания экзаменов: 1. Не менее 2 дней для подготовки к экзамену. 2. Не более 6 часов на экзамен для одной группы. 3. Не менее 2 часов на консультацию перед экзаменом. 4. Экзаменов в году не более 8, зачётов не более 10. 5. Время на сдачу устного экзамена - не более 15 минут. 6. Время на сдачу комплексного экзамена - не более 23 минут на одного студента. 7. Время на сдачу письменного экзамена - не более 3 часов (академических). 8. Время на выполнение задания билета - не более 1 часа (академического). 9. Время консультации перед комплексным экзаменом - не менее 2 часов на дисциплину, входящую в программу экзамена. Алгоритмы составления расписания должны опираться на ряд ограничений основного и второстепенного значения. Качество расписания оценивается через систему показателей, которые отражают уровень удовлетворенности заданным ограничениям. После учёта основных требований по составлению расписания учитываются второстепенные требования, в том числе пожелания преподавателей по проведению занятий (количество дней, определенные дни недели, определенная половина дня недели - особенно это актуально для внештатных преподавателей), географическое расположение корпусов (аудиторий) вуза для обеспечения минимума переходов студентов (преподавателей) между занятиями из аудитории в аудиторию, количество «окон». Тем самым преподаватели определяют множество запретов или ограничений на множестве требований, которые представляют собой векторы значений целевых функций. Требования, преподаватели и атрибуты аудиторий могут быть проранжированы. Определенные требования могут быть объединены в один обобщенный показатель качества на основе различных метрик. Обзор существующих методов для решения задачи составления расписаний и имеющихся программных разработок Задача составления расписания принадлежит классу NP-полных задач и может быть решена на базе таких различных подходов и методов, как: - классические методы в терминах целочисленного линейного программирования или задачи о раскраске графа [8-11]; - метаэвристические методы - метод имитации отжига, генетические алгоритмы и др. [7, 12, 15, 17, 18]; - мультиагентные системы, метод решения по прецедентам [13-15]. Обобщенный алгоритм составления расписания Систем для автоматического составления расписания достаточно много, например «Астра», «1С: ХроноГраф Расписание», «АВТОРасписание» и др. Практика показывает, что среди существующих систем больше тех, которые используются для первоначальной расстановки предметов и элементов расписания (обычно от 40 до 70 %) с последующей ручной доработкой [25]. Существующие программы ориентированы в основном на школы, колледжи и не всегда могут быть адаптированы к реалиям вуза, кроме того, они отличаются высокой стоимостью. Алгоритмы формирования расписания основаны на переборах вариантов с проверкой качества расписания на базе разных эвристик для облегчения и ускорения процедуры поиска. Особый интерес представляют эвристические алгоритмы, не имеющие строгого математического обоснования, но демонстрирующие приемлемое качество решения на практике. Так, опыт сотрудников учебного отдела показывает, что формирование расписания начинают с распределения предметов «первостепенных» - физкультура, иностранный язык и др. Далее имеет место декомпозиция задачи составления расписания в зависимости от множества участников, включенных в текущее распределение. Задача разбивается на части или, точнее, на ряд последовательно решаемых задач, при этом каждая задача, решенная на предыдущем шаге, является ограничением для задачи, подлежащей решению на следующем шаге. Потом, при доработке расписания, текущее расписание может видоизменяться по мере включения в распределение все большего количества новых участников. Соответственно, нужно определить величины, задающие уровень уступки в требованиях при изменении варианта расписания. Кроме того, необходимо определить целевую функцию, объединив структуру показателей качества расписания в ней. Обобщённый алгоритм составления расписаний представлен на рис. 3 со следующими обозначениями: Ns - число дисциплин обучения; Ng - число учебных групп; Nt - число преподавателей; Na - число аудиторий; Np - число пар в течение семестра; Nd - множество требований; - матрица разрешений: - матрица запретов: ; Ksпорог, Ktпорог - пороговые значения; Psпорог, Ptпорог - приоритеты дисциплин и преподавателей. Рис. 3. Обобщённый алгоритм составления расписаний Предложенный обобщенный алгоритм составления расписания учитывает результаты ряда научных исследований, касающихся решения задач теории расписания. Заключение В ходе исследований было сформировано множество показателей оценки качества расписания, представлены способы свертки критериев для упрощения процедуры выбора удовлетворительного расписания. Предложен обобщенный алгоритм составления расписания, учитывающий различные научные исследования, связанные с решением задач теории расписания. В настоящее время количество требований при формировании расписаний растет, вследствие чего автоматизированные комплексы необходимо перестраивать. Решение задачи по автоматическому формированию расписания сэкономит трудозатраты сотрудников учебных отделов, обеспечит принципы справедливости при составлении расписания, создаст максимально удобные условия для преподавательской деятельности, которая не ограничивается аудиторной нагрузкой. Создание расписания - это не одномоментный акт, во время учебного процесса может понадобиться доработка расписания, чтобы обеспечить замену преподавателей при увольнении, нахождении в командировке или при болезни коллег. Очевидно, что развитие базы знаний правил для автоматической генерации расписаний по-прежнему остается актуальной задачей.
References

1. Ob obrazovanii v Rossiyskoy Federacii: feder. zakon ot 29 dekabrya 2012 g. N 273-FZ (v red. Federal'nyh zakonov ot 07.05.2013 N 99-FZ, ot 07.06.2013 N 120-FZ, ot 02.07.2013 N 170-FZ, ot 23.07.2013 N 203-FZ, ot 25.11.2013 N 317-FZ, ot 03.02.2014 N 11-FZ, ot 03.02.2014 N 15-FZ, ot 05.05.2014 N 84-FZ). N 273-FZ). URL. http://www.consultant.ru/document/cons_doc_LAW_140174/.

2. Ob utverzhdenii poryadka organizacii i osuschestvleniya obrazovatel'noy deyatel'nosti po obrazovatel'nym programmam vysshego obrazovaniya - programmam bakalavriata, programmam specialiteta, programmam magistratury: prikaz Minobrnauki Rossii ot 19.12.2013 N 1367. URL: http://www.garant.ru/ products/ipo/prime/doc/70503294/.

3. Hahn-Goldberg S. Defining, Modeling, and Solving a Real University Course Timetabling. URL: http://tidel.mie.utoronto.ca/pubs/Theses/hahn-goldberg.masc.pdf.

4. Konvey R. V., Maksvell V. L., Miller L. V. Teoriya raspisaniy. M.: Nauka, 1975. 360 c.

5. Crainic T. G., Toulouse M. Parallel Meta-heuristics. Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT-2009-22). Canada, 2009. 51 p.

6. Burke E. K., Marecek J., Parkes A. J., Rudova H. A supernodal formulation of vertex colouring with applications in course timetabling // Annals of Operational Research. 2010. Vol. 179, No. 1. P. 105-130.

7. Kuhn F. Weak Graph Colorings: Distributed Algorithms and Applications // SPAA '09 Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures. 2009. P. 138-144.

8. Burke E. K., Marecek J., Parkes J., Andrew J., Rudova H. Penalising Patterns in Timetables: Novel Integer Programming Formulations. In: Operations Research Proceedings 2007. Berlin: Springer, 2008. P. 409-414.

9. Boehning R. L., Butler R. M., Gillett B. E. A parallel integer linear programming algorithm // European Journal on Operations Research. 1988. Vol. 34, iss. 3. P. 393-398.

10. Abdullah S., Hamdan A. R. A Hybrid Approach for University Course Timetabling // International Journal of Computer Science and Network Security. 2008. Vol. 8, No. 8. P. 127-131.

11. Babkin E., Abdulrab H., Babkina T. Agent Time: A Distributed Multi-agent Software System for University’s Timetabling. Ma Aziz-Alaoui & C. Bertelle (eds.). From System Complexity to Emergent Properties. Heidelberg, Springer, 2009. P. 141-154.

12. Autry B. M., Squire K. University course timetabling with probability collectives. URL: http://bosun.nps.du/ uhtbin/hyperion-image.exe/08Mar_Autry.pdf.

13. Burke E. K., Petrovic S., Qu R. Case-based heuristic selection for timetabling problems // Journal of Scheduling. 2006. Vol. 9, No. 2. P. 115-132.

14. Yu E., Sung K. S. A genetic algorithm for a university weekly course timetabling // International Transactions In Operational Research. 2002. Vol. 9. P. 703-717.

15. Nandhini M., Kanmani Dr. S. A Survey of Simulated Annealing Methodology for University Course Timetabling // International Journal of Recent Trends in Engineering. 2009. Vol. 1, No. 2. P. 255-257.

16. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by Simulated Annealing // Science. New Series. 1983. Vol. 220, No. 4598. P. 671-680.

17. Davydov S. V. Sistema avtomaticheskogo postroeniya raspisaniya uchebnyh zanyatiy. URL: http://davidovsv narod.ru/schedule/index.html.

18. Beregovyh Yu. V., Vasil'ev B. A., Volodin N. A. Algoritm sostavleniya raspisaniya zanyatiy // Iskusstvennyy intellekt. 2009. № 2. S. 35-43.

19. Verevkin V. I., Ismagilova O. M., Atavin T. A. Avtomatizirovannoe sostavlenie raspisaniya uchebnyh zanyatiy vuza s uchetom trudnosti disciplin i utomlyaemosti studentov // Dokl. Tomsk. gos. un-ta sistem upravleniya i radioelektroniki. 2009. № 1 (19), ch. 1. S. 221-225.

20. Baltak S. V., Sotskov Yu. N. Postroenie raspisaniy uchebnyh zanyatiy na osnove raskraski vershin grafa // Informatika. 2006. № 3 (11). S. 56-69.

21. Kabal'nov Yu. S., Shehtman L. I., Nizamova G. F., Zemchenkova N. A. Kompozicionnyy geneticheskiy algoritm sostavleniya raspisaniya uchebnyh zanyatiy // Vestn. Ufim. gos. aviac. tehn. un-ta. 2009. T. 7, № 2 (15). S. 99-107.

22. Yandybaeva N. V. Geneticheskiy algoritm v zadache sostavleniya uchebnogo raspisaniya vuza // Sovremennye naukoemkie tehnologii. 2009. № 11. S. 97-98.

23. Sousa F., Alves A. Polnost'yu evristicheskoe raspisanie zanyatiy, upravlyaemoe pozhelaniyami studentov // Naukovі pracі Vіnnic. nac. tehn. un-tu. 2009. № 2. S. 1-4.

24. Shishkanova T. A. Razrabotka metodiki postroeniya avtomatizirovannoy sistemy upravleniya uchebnym processom. URL: http://www.giab-online.ru/files/Data/2013/12/366-372_SHishkanova_-_7_str.pdf.

25. Pilikov N. P. Problema polnoy avtomatizacii pri sostavlenii shkol'nogo raspisaniya. URL: http://www.mnogosmenka.ru/pilikov/timetable.htm.

This work is licensed under Creative Commons Attribution 3.0 Unported

Support Powered by Editorum,  Instructions
Login or Create
* Forgot password?