در تحقیقات پیشین جدول زمانبندی دانشگاه به عنوان یک مساله عملیاتی مورد مطالعه قرار گرفته است؛ که هدف، اختصاص دادن سخنرانی به اتاق ها و زمان بندی و ایجاد جداول زمانی با کیفیت برای دانشجویان و اساتید است. پیش از آن که این موضوع حل شود، دو مشکل تصمیم گیری مهم پیش می آید: چه اتاق هایی لازم است و در کدام دوره های تدریس؟ این تصمیمات ممکن است اثری قوی بر جداول زمانی حاصل داشته باشد و به ندرت تغییر کند و یا حتی مورد بحث قرار گیرد. این مقاله بر حل این دو مشکل راهبردی تمرکز می کند و اثر این تصمیمات بر کیفیت جداول زمانی حاصل را بررسی می کند.

رابطه و تفاوت های بین مسائل اجرایی، تاکتیکی و راهبردی بازنگری می شوند. بر اساس تدوین زمانبندی و مطالب دوره های مبتنی بر سرفصل دروس از دومین رقابت جدول زمانی بین المللی (ICT 2007)، سه مدل عدد صحیح مختلط دو هدفه تدوین می شود. برای حل آن ها، الگوریتمی را بر اساس روش محدودیت ϵ- پیشنهاد می دهیم. این الگوریتم می تواند برای تحلیل اثر داشتن منابع مختلف در مسائل جدول زمانی مورد استفاده قرار گیرد. در نهایت ما نتایج مربوط به نحوه تاثیر این سه هدف (اتاق، دوره های تدریس، و کیفیت) بر یکدیگر را گزارش می کنیم.

کلمات کلیدی: جدول زمانی، برنامه ریزی هدف چندگانه، برنامه ریزی عدد صحیح

مقدمه

برنامه‌ریزی و زمان‌بندی آموزشی توجه زیادی را در تحقیقات عملیاتی به خود جلب کرده است و برای مدت‌های طولانی مورد مطالعه قرار گرفته است؛ برای یک بررسی و مرور در این زمینه بنگرید به کینگستون (۲۰۱۳) و کریستینسن و استیدسن (۲۰۱۳). بسیاری از تغییرات در این مسئله وجود داشته است، زیرا این بین مراحل مختلف آموزش در کشورهای مختلف متفاوت است. تعریفی که معمولا برای تنظیم زمان‌بندی مورد استفاده قرار گرفته شده است، از رِن (۱۹۹۶) بدست آمده است:

“زمان‌بندی، تخصیص با توجه به محدودیت منابع معین در اشیائی است که در فضا زمان قرار می‌گیرند، بطوری که بتواند مجموعه‌ای از اهداف مطلوب را تا جایی که امکان دارد نزدیک به هم برآورده نماید”.

این تعریف، مشکلات مربوط به زمان‌بندی را که معمولا در ادبیات مورد بررسی قرار می‌گیرند، در بر می‌گیرد. با این وجود، دیگر تصمیمات مهم مربوطه به ندرت مورد بررسی قرار می‌گیرند. به عنوان مثال: کدام منابع باید در دسترس باشند؟ کجا در فضا و زمان مجاز به قرار دادن این اشیاء هستیم؟ در این مقاله، ما مدل‌ها و روش‌هایی را برای تصمیم‌گیری در مورد این که چه اندازه اتاق‌ها و دوره‌های آموزشی باید توسط یک سازمان استفاده شود، ایجاد می‌کنیم و تحلیل می‌کنیم که چگونه این تصمیمات براساس جدول زمانی حاصله موثر خواهد بود.

یک مرور کلی از مشکلات تصمیم‌گیری مربوط به زمان‌بندی در شکل ۱ نشان داده شده است. ارزش یک جدول زمانی که از طریق حل این مسائل بدست می‌آید، با سه مقیاس مرتبط با فرایند زمان‌بندی مشخص می‌شود:

چابکی . پاسخ به تغییرات و اعمال سریع تغییرات در جدول زمان‌بندی.

کیفیت. یک جدول زمانی که محیط کار خوبی را برای کارکنان و دانشجویان ارائه می‌دهد.

هزینه. یک جدول زمانی که از منابع پر هزینه استفاده می‌کند.

Abstract

University timetabling has traditionally been studied as an operational problem where the goal is to assign lectures to rooms and timeslots and create timetables of high quality for students and teachers. Two other important decision problems arise before this can be solved: what rooms are necessary, and in which teaching periods? These decisions may have a large impact on the resulting timetables and are rarely changed or even discussed. This paper focuses on solving these two strategic problems and investigates the impact of these decisions on the quality of the resulting timetables.

The relationship and differences between operational, tactical and strategic timetabling problems are reviewed. Based on the formulation of curriculum-based course timetabling and data from the Second International Timetabling Competition (ITC 2007), three new bi-objective mixed-integer models are formulated. We propose an algorithm based on the ϵ-constraint method to solve them. The algorithm can be used to analyze the impact of having different resources available on most timetabling problems. Finally, we report results on how the three objectives – rooms, teaching periods, and quality – influence one another.

Keywords Timetabling,Multiple objective programming,Integer programming

۱. Introduction

Educational timetabling has gained a lot of attention within op- erations research and has been studied for a long time; for an overview see Kingston (2013) and Kristiansen and Stidsen (2013) . Many variations of the problem exist as it varies between different educational stages and countries. A definition commonly used for timetabling comes from Wren (1996) : “Timetabling is the allocation, subject to constraints of given re- sources to objects being placed in space time, in such a way as to satisfy as nearly as possible a set of desirable objectives.”

This definition captures the timetabling problems that are usu- ally investigated in the literature. However, other important related decisions are rarely investigated. For example: Which resources should be available? Where in space and time is it allowed to place these objects? In this paper, we create models and methods to de- cide what room sizes and teaching periods should be used by an organization, and analyzes how these decisions affect the resulting timetable. An overview of the decision problems that relate to timetabling are illustrated in Fig.1 The value of a timetable obtained by solving these problems is characterized by three measures associated with the timetabling process: Agility.

Responding to changes and quickly make alterations to the timetable. Quality. A timetable that gives a good work environment for employees and students. Cost. A timetable which uses costly resources efficiently. We categorize each of these problems as either operational, tactical or strategic. The strategic problems are the ones that are solved first and which then affect the tactical problems that are solved next. Finally, the operational problems are solved last.

The problems we find at each level, as shown in Fig. 1 , are as follows: Operational. The operational problems are the ones that result in final timetable, i.e. deciding which lectures should be taught in what rooms and when. This main problem is solved every semester, and we separate it into two closely related cases. The first case is the assignment problem , which is the feasibility prob- lem of finding a conflict-free timetable. A common addition to this problem, which is the second case, is including quality measures that aim to make a desirable timetable for students and staff, i.e. the Quality problem . Soft con- straints are used in this case, where the violation of these should be minimized. Both course timetabling problems for the Second International Timetabling Competition, formulated in Di Gaspero, McCollum, and Schaerf (2007) , fall into this second category.

After a timetable is put into production, disruptions will of- ten occur during the semester as alterations need to be made. Handling such disruptions requires solving the minimal perturba- tion problems addressed in Muller, Rudová, and Barták (2005) and Phillips, Walker, Ehrgott, and Ryan (2014) . When decision-support tools are used to solve these problems, it provides agility by be- ing able to create the timetable more quickly and respond faster to changes.

Tactical. The tactical problems involve the decisions that are taken before creating the actual assignments. This includes, for example, to prioritize the different quality measures or how to divide the timetabling workload between multiple planners. These decisions affect the quality because a course could end up being taught in an undesired timeslot because the planner does not have other rooms available, even though there may be free rooms in another part of campus. Strategic. The strategic problems are the long-term decisions that affect the timetable and have a high impact on the organization. This could, for example, be to allow teaching to be scheduled later in the day by adding additional timeslots, which we define as the Teaching Periods problem.