نوع مقاله : مقاله پژوهشی
نویسندگان
1 گروه ریاضی، دانشگاه پیام نور، تهران، ایران.
2 گروه ریاضی، موسسه آموزش عالی توس، مشهد، ایران.
چکیده
هدف: به‌منظور حل مسئله اختصاص دبیران به مدارس، در قالب یک مدل ریاضی با استفاده از یک رویکرد ابتکاری مبتنی بر الگوریتم ژنتیک اصلاحی به دنبال افزایش رضایت‌مندی دبیران هستیم.
روش‌شناسی پژوهش: در این مقاله با استفاده از الگوریتم ژنتیک ساختگرا (CGA)، در یک‌زمان معقول علاوه بر تخصیص مناسب دبیران به مدارس، افزایش رضایت‌مندی آن‌ها را نیز به دنبال دارد. این نوع الگوریتم شامل چند ویژگی جدید مانند جمعیت تشکیل‌شده از طرح‌واره، ترکیب مجدد بین طرح‌واره، اندازه جمعیت پویا، جهش در کروموزوم‌های کامل، احتمال استفاده از اکتشافات در طرح‌واره و یا نمایش کروموزوم را ارائه می‌دهد. طرح‌واره‌ها، برخلاف کروموزوم‌ها تمام اطلاعات مربوط به داده‌های مسئله را در برنمی‌گیرند. با ترکیب طرح‌واره‌ها، طرح‌واره یا کروموزوم‌های جدید به وجود می‌آیند. طرح‌واره‌های جدید برمبنای یک آزمون ارزیابی از پیش تعیین‌شده، ارزیابی می‌شوند و چنانچه در آن صدق کنند شرایط بقا را دارا می‌باشند و به جمعیت اضافه می‌شوند. برخلاف الگوریتم‌های تکاملی دیگر که ارزیابی افراد بر اساس یک تابع تناسب تعریف می‌شود، در CGAاین فرایند مشتمل بر استفاده از دو تابع f و g است.
یافته‌ها: الگوریتم موردبررسی ازنظر شاخص‌های زمان، سرعت اجرا و کارایی و همچنین انعطاف‌پذیری مسئله نسبت به روش سنتی برتر است. این الگوریتم از بین جواب‌های بهینه متعدد، جوابی را با تعداد اختصاص‌های بیشتر به‌عنوان جواب نهایی انتخاب می‌کند. یکی از مزایای الگوریتم پیشنهادی تعمیم‌پذیری و انعطاف‌پذیری آن است که می‌تواند به‌سادگی با تغییر محدودیت‌های موجود در مسئله جواب‌های متنوع مناسبی را تولید کرد.
اصالت/ارزش افزوده علمی: الگوریتم پیشنهادی برای تخصیص دبیران به مدارس برای یک سال تحصیلی برای اولین بار بر روی نمونه مطالعاتی دبیرستان‌های پسرانه شهرستان تربت‌جام اجرا شد.
کلیدواژه‌ها
موضوعات
عنوان مقاله [English]
Teachers Timetabling in Torbat-E-Jam Schools Using Constructive Genetic Algorithm
نویسندگان [English]
- Hamid Reza Yousefzadeh 1
- Mahdi Masumi 2
1 Department of Mathematics, Payame Noor University (PNU), Tehran, Iran.
2 Department of Mathematics, Toos Institute Higher Education, Mashhad, Iran.
چکیده [English]
Purpose: In order to solve the problem of assigning teachers to schools, in the form of a mathematical model using an innovative approach based on Constructive Genetic Algorithm (CGA), we seek to increase teachers' satisfaction.
Methodology: In this paper, using the Constructive Genetic Algorithm (CGA), in a reasonable time, in addition to the appropriate allocation of teachers to schools, also increases their satisfaction. This type of algorithm includes several new features such as population consisting of schema, recombination between schema, dynamic population size, mutation in chromosomes, and possibility of using schema discoveries or chromosome representation. Schemas, unlike chromosomes, do not contain all the information about the problem data. By combining schemas, new schemas or chromosomes are created. New schemas are evaluated based on a predetermined assessment test, and if they are valid, they have the conditions to survive and are added to the population. Unlike other evolutionary algorithms in which the evaluation of individuals is defined on the basis of proportionality function, in CGA, this process involves the use of two functions, f and g.
Findings: The proposed algorithm is superior to the traditional method in terms of time, execution time and efficiency as well as flexibility of the problem. This algorithm selects the solution with the highest number of attributes as the final solution among several optimal solutions. One of the advantages of the proposed algorithm is its generalizability and flexibility, which can easily produce suitable various solutions by changing the existing constraints on the problem.
Originality/Value: The proposed algorithm for assigning teachers to schools for one academic year was implemented for the first time on the case study of boys' high schools in Torbat-e-Jam city.
کلیدواژه‌ها [English]
- Time table
- Scheduling
- Mathematical programming
- Meta-heuristic algorithm
)