نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 کارشناسی ارشد، گروه مدیریت، دانشگاه اصفهان
2 دانشیار، گروه مدیریت، دانشگاه اصفهان
3 استادیار، گروه مدیریت، دانشگاه اصفهان
چکیده
کلیدواژهها
عنوان مقاله [English]
نویسندگان [English]
University course timetabling problem is a challenging and time-consuming task on the overall structure of timetable in every academic environment. The problem deals with many factors such as the number of lessons, classes, teachers, students and working time, and these are influenced by some hard and soft constraints. The aim of solving this problem is to assign courses and classes to teachers and students, so that the restrictions are held. In this paper, a constraint programming method is proposed to satisfy maximum constraints and expectation, in order to address university timetabling problem. For minimizing the penalty of soft constraints, a cost function is introduced and AHP method is used for calculating its coefficients. The proposed model is tested on department of management, University of Isfahan dataset using OPL on the IBM ILOG CPLEX Optimization Studio platform. A statistical analysis has been conducted and shows the performance of the proposed approach in satisfying all hard constraints and also the satisfying degree of the soft constraints is on maximum desirable level. The running time of the model is less than 20 minutes that is significantly better than the non-automated ones.
کلیدواژهها [English]
مسئلۀ جدول زمانبندی دروس دانشگاهی([1]UCTP)، در زمرۀ مسائل مهم و زمانبر در هر محیط آموزشی بهشمار میآید. زمانبندی و برنامهریزی چیدمان دروس در جدول هفتگی، براساس معیارها و امکانات محیط، مشخصات دروس و ساعات حضور استادان صورت میگیرد. بهطور کلیUCTP، عبارت است از انتساب ساعات تدریس استادان و نیز کلاسهای موجود به یک مجموعه بازۀ زمانی؛ بهنحوی که در مجموعهای از شرایط صدق کند (کازارلیس[2] و همکاران، 2005). در یکUCTP، برگزاری همزمان دو درس با دانشجویانیک گروه آموزشییا تدریسیک استاد در یک بازۀ زمانییکسان با دروس متفاوت را تداخل گویند. در حالت کلی هدف از بررسی، کاهش تعداد تداخل بین دروس دانشجویانیک گروه آموزشی و یا تدریسیک استاد و همچنین رفع همزمانی دروسی است که به یک اتاق مشترک نیاز دارند(لوئیس[3]، 2008). با افزایش تعداد محدودیتهای برنامهریزی، رسیدن به یک جواب قابلِقبول، بسیارمشکل خواهد بود؛ بنابراین هدف زمانبندی دروس، ایجادیک برنامۀ زمانی معتبر و قابلاجرا با حداقل تداخل است.
مسئلۀ زمانبندی دروس دانشگاهی در همۀ حالات از نظر پیچیدگی محاسباتی به کلاس NP–hard تعلق دارد؛ بنابراین الگوریتمی با پیچیدگی زمانی از مرتبۀ چندجملهای برای حل آن ارائه نشده است. برای حل مسائل زمانبندی میتوان از الگوریتمهای دقیق و الگوریتمهای تقریبی استفاده کرد. الگوریتمهای دقیق برای حل اینگونه مسائل، غیرعملیهستند؛ چرا که زمان اجرای این دسته از الگوریتمها با رشد اندازۀمسئله بهصورت نمایی افزایش مییابد(گری و جانسون[4]، 2002)؛ بنابراین از الگوریتمهای تقریبی مانند الگوریتمهای ابتکاری و فراابتکاری استفاده میشود. از جملۀ این الگوریتمها میتوان به الگوریتمهای ژنتیک[5]، جستجوی ممنوع[6] وکلونی زنبورعسل[7] اشاره کرد. (یانگ و جَت[8]، 2011)،(لو و هاو[9]، 2010)،(صابَر و همکاران[10]، 2012) و(میرحسنی، 2006).
یکی دیگر از رویکردهای حلمسائل جدول زمانبندی، برنامهریزی محدودیت است. این رویکردیک الگوی حل مسئله است که میان محدودیتهایمسئله و الگوریتمهای جستجو تمایز قائل شده است(ماریوت و استاکی[11]، 1998). الگوریتمهای جستجو اغلب با استفاده از شناسایی حالات متفاوت محدودیتها و الگوریتمهای انتشار محدودیت[12]، ممکن میشود.
مسائل ارضای محدودیت ([13]CSP)، چارچوبی واحد برای مسائل مختلف محاسباتی که ماهیتاً در حوزۀ هوشمصنوعی و بهینهسازی ترکیبیاتی هستند، ارائه میکند.این مسائل کهنمونهای از مسائل با دامنۀ محدود است، لیستی از متغیرها و محدودیتها را شامل میشود؛ بهطوریکه مقادیر ممکن از دامنه را به متغیرها مرتبط میکند و بیان میکند که آیا متغیرها قادر هستند مقادیریبگیرند که بهطور همزمان همۀ محدودیتها را ارضاکنند یا خیر (زیونی[14]، 2012).
در ادامۀ مقاله و در بخش دوم خلاصهای از کارهای صورتگرفته در حوزۀ جدول زمانبندی آموزشی آمدهاست. بخش سوم مفاهیم مسئله جدول زمانبندی و رویکردهای حل آن بههمراه برنامهریزی محدودیت، مسئلۀ ارضای محدودیت و الگوریتمهای جستجوی آن بیان شده است. در بخش چهارم مدل پیشنهادی تشریح میشود. بخش پنجم به مطالعۀموردی پژوهش اختصاص یافته و در بخش ششم نتایج بهدستآمده از پیادهسازی مدل در مطالعۀ موردی بررسی قرار گرفته میشود. در بخش هفتم مقاله، پیشنهادهایی جهت کارهای آینده ارائه میشود.
در چند دهۀ گذشته پژوهشگران وگروههای پژوهشی هوشمصنوعی و پژوهش عملیاتی، تلاشهای بسیاری بهمنظور خودکارسازی روند زمانبندی انجام دادهاند(بارتاک[15]، 2000) و (ریس و الیویرا[16]، 2001).ماریوت و اسکاتی(1998) منطق برنامهریزی محدودیت را برای زمانبندی امتحانات دانشگاهی بهکار گرفتند.پژوهش آنها تأییدی بر پتانسیل منطق برنامهریزی محدودیت برای نمونهسازی و اجرای برنامههای کاربردی در زندگی واقعی بود. آنها همچنین توانایی بهکارگیری بیش از 3000 محدودیت را از ویژگیهای برتر برنامهریزی محدودیت برشمردند. روادا و مری[17] (2003) از محدودیتهای وزندار در مدل برنامهریزی محدودیت خود برای حل این مسئله استفاده کردند. این مدل بهطور کلی برای هر نوع محدودیت اولویت قائل میشود و موجودیتهای درون هر محدودیت را وزندار نکرده است.لو و هاو (2010) در پژوهش خود یک الگوریتم جستجوی ممنوع تطبیقی برای حل مسئلۀ زمانبندی دروس ارائه داد.نتایج بهینهبودن این الگوریتم با پیادهسازییک مجموعه دادۀ مشخص بههمراه مقایسۀ آن با سایر الگوریتمها نیز در پژوهش آمده است .صابر و همکاران(2012) یک الگوریتم بهینهسازیکلونیزنبورعسل را برای حل مسئلۀ زمانبندی دروس دانشگاهی ارائه کردند. نتایج بهدستآمده از پیادهسازی این الگوریتم بر جدول زمانبندی امتحانات و دروس نشان میدهد که اینالگوریتم، قابلاعتماد است و برای حل مسائل زمانبندی، دانشگاه معتبر خواهد بود .البتر و همکاران[18](2012) در پژوهش خود از الگوریتم ممتیک[19] برایمسئلۀ زمانبندی دروس دانشگاهی استفاده کردند.در این رویکرد، یک الگوریتم جستجوی هماهنگ ترکیبی(HHSA[20])بهکار گرفته شده است؛بهگونهای که الگوریتمHSAکه یک رویکرد فراابتکاری مبتنی بر جمعیت است اولاً با الگوریتم تپهنوردی[21] ترکیب شده تا بتواند کاوش محلی خود را توسعه دهد و ثانیاً با الگوریتم بهینهسازی ازدحام ذرات[22] ترکیب میشود تا همگرایی را ارتقا دهد. نتایج حاصل از این پیادهسازی بهینهبودن این رویکرد را نشان میدهد؛ بنابراین پیشبینی شده است این رویکرد برای مجموعه دادههای پیچیده نیز جوابی بهینه حاصل کند.هواس و همکاران[23](2013) مدلی برای حل مسائل زمانبندی دروس دانشگاهی با استفاده از برنامهریزی عدد صحیح ارائه دادند. در این مدل محدودیتها، نیازمندیهای جدول زمانبندی را برای ایجاد یک زمانبندی معتبر، مهیا میکنند. همچنین در این پژوهش، تابع هدف، انعکاس ترجیحات دانشجویان و استادان است.نتایج حاصل از پژوهش نشاندهندۀ ارضای تمامی محدودیتهای سخت و نرم است .منجمی و همکاران (1385) در پژوهش خود از خصوصیات الگوریتم ژنتیک بهعنوان ابزاری مناسب در بهینهسازی پاسخهای یک مسئلهCSPاستفاده کردهاند. نتایج حاصل نشان میدهد الگوریتم ژنتیک پیشنهادی در طراحی جداول زمانبندی خوشساخت برای یک دانشکدۀ مفروض بهخوبی عمل میکند.رحمانی (1386) در پژوهش خود، الگوریتم ممتیک را ارائه کرد. این الگوریتم نسبت به الگوریتم ژنتیک نتایج بهتری داشت. نتایج حاصل، گویای این است که روش پیشنهادی این پژوهش، میتواند بر روند اجرای الگوریتم تأثیر بسیار مؤثری داشته باشد و همچنین زمان همگرایی کروموزومها را به سمت پاسخ بهینه به حداقل برساند. غافری (1389) در پژوهش خود درزمینۀ زمانبندی دروس دانشگاهی، رویکرد استفاده از گرافها را در پیش گرفته است. در این رویکرد برای ارضای تعدادی از محدودیتهای سخت از الگوریتم رنگآمیزی گراف و سپس، سایر محدودیتهای سخت و نرم توسط الگوریتم ژنتیکبهکاررفته در حین استفاده از الگوریتم رنگآمیزی استفاده شده است. این عمل باعث بالاتررفتن احتمال حصول نتیجۀ الگوریتم رنگآمیزی گراف و بالاتررفتن سرعت بهنتیجهرسیدن الگوریتم ژنتیک شده است.رستگارامینی و همکاران (1391) در پژوهش خود، یک مدل ریاضی صفریک برای مسئلۀ زمانبندی آموزشی ارائه دادند. در این مدل، ترجیحات استاد دربارۀ بازههای زمانی، موضوعات درسی و یک تابع هدف جدید که کمینهسازی تعداد دروس همزمان با دانشجویان مشترک میسر میسازد، ارائه شده است. کارایی روش مطرحشده با افزایش ابعاد مسئله کاهش مییابد؛ بنابراین یک الگوریتم فراابتکاری سیستم کلونی مورچگان برای حل این مسئله ارائه شده است.
در این بخش ابتدا مفاهیم اولیۀ برنامهریزی آموزشی مطرح شده، رویکردهای حل آن بهطور مختصر معرفی میشود و سپس برنامهریزی محدودیت و مفاهیم موجود در آن بیان میگردند.
1-3- مسئلۀ جدول زمانبندی آموزشی
طراحی و پیادهسازی جدول زمانبندی دانشگاهی، نیازمند انطباق با نیازها و قوانین دانشگاه و ذینفعان است. در بسیاری از دانشگاهها، حل مسائل جدول زمانبندی به عهدۀ مسئولان آموزش است. این برنامه با سعی و خطا حاصل شده است و مسلماً راهحل مناسبی برای حل اینگونه مسائل نخواهد بود. در چنین شرایطی میتوان با بهرهگیری از فناوریهای مهندسی و ریاضی، سیستمی مکانیزه ارائه کرد که بهصورت خودکار بتواند جدول زمانبندی را حل کند (میرحسنی، 2006).
پژوهشگران، محدودیتهای موجود در یکمسئلۀ جدول زمانبندی دروس دانشگاهی را به دو دسته تقسیمبندی کردهاند (لیس و میکلون[24]، 2008):
1) محدودیتهای سختکه نقض آنها منجر به امکانناپذیری برنامۀ هفتگییا نامطلوبشدن آن بهمیزان زیاد میشود. نمونهای از این محدودیت، تداخل زمانی دو درس در یک اتاق است؛
2)محدودیتهای نرم که قابلیت نقضشدن دارند، ولی نقض هرکدام از آنها از مطلوبیت برنامه میکاهد. محدودیتهای نرم، به آن دسته از محدودیتهایی اطلاق میشود که به سیاستهای دانشگاه و نیاز افراد توجه دارد؛ رعایت این محدودیتها مطلوب بوده اما ارضای آنها اجباری نیست.در مجموع، محدودیتهای سخت دارای اولویت بالاتری نسبت به محدودیتهای نرم هستند و یک جدول زمانبندی، زمانی قابلقبول است که همۀ محدودیتهای سخت آن ارضا شده باشند. هرچه محدودیتهای نرم بیشتر ارضا بشنود، جدول زمانبندی حاصل، از مطلوبیت بیشتری برخوردار خواهد بود. دربخش بعد رویکردهای حل مسئلۀ جدول زمانبندی دروس دانشگاهی آمده است.
با نگاه کلی به مسئلۀ جدول زمانبندی دانشگاهی، برداشت میشود که برای حل مسائل جدول زمانبندی لازم است در ابتدا توصیفی از مسئله وجود داشته باشد. بعد از توصیف، مسئله باید پیشپردازش شود. در این مرحله اعتبار دادهها بررسی میشود، همچنین مسئله به چند بخش برای حل سادهتر تقسیم میشود. سپس متناسب با هر بخش الگوریتمی بهمنظور حل آن انتخاب میشود و درنهایت جواب نهایی حل جدول زمانبندی شکل میگیرد. رویکردهای بسیاری برای حل مسائل جدول زمانبندی وجود دارند؛ از جملۀ این رویکردها میتوان به برنامهریزی خطی([25]LP)، رویکردهای ابتکاری و فراابتکاری اشاره کرد که سابقهای طولانی در اینگونه مسائل دارند (میرحسنی، 2006). بروک و پترویک[26] (2002) ، یک تقسیمبندی دقیق از رویکردهای موجود در حل مسائل جدول زمانبندی ارائه کردهاند که شامل موارد زیر است:
1) رویکرد ترتیبی: در این رویکرد، ابتدا وقایع بهکمک دامنههای اکتشافی موجود مرتب میشوند. سپس این وقایع در بازههای زمانی قرار داده میشوند. این تخصیص و قرارگیری بهگونهای است که تداخلی پیش نیاید (کارتر[27]، 1986). برای حل مسائل زمانبندی با این رویکرد از روش رنگآمیزی گراف استفاده میشود. در این رویکرد گرهها نمایانگر ساعات درسی و یالها نشاندهندۀ تداخل میان این ساعات هستند. درنهایت گراف باید بهگونهای رنگآمیزی شود که هیچ دو گره مجاوری، رنگ یکسان نداشته باشند.این رویکرد بازده زمانی خوبی ندارد (زیربان[28]، 2007).
2) رویکرد خوشهبندی: این رویکرد در حل مسائل جدول زمانبندی به این صورت است که رویدادها را به گروههایی تقسیم میشوند که در ابتدا محدودیتهای سخت را ارضا کنند و سپس گروهها با ارضای محدودیتهای نرم به بازههای زمانی تخصیص مییابند. پیداکردن راهحل بهکمک این رویکرد سریع است؛ اما در بعضی مواقع ممکن است بهدلیل وابستگیهای زیاد میان رویدادهای جدول زمانبندی، نتایج ضعیفی را حاصل کند.
3) رویکرد ابتکاری و فراابتکاری: طیف گستردهای از این رویکردها، بهصورت رویکردهای ترکیبی کاربرد دارند. این رویکردها با یک سری راهحل ابتدایی آغاز میشوند و سپس با بهکارگیری استراتژیهای جستجو سعی در پیداکردن راهحل نهایی دارند. تمامی این الگوریتمهای جستجو میتوانند جوابهایی با کارایی بالا ایجاد کنند؛ اما معمولاً ازلحاظ محاسباتی به صرفه نیستند (بروک و پترویک، 2002).
4) رویکرد مبتنی بر محدودیت: این رویکرد، یک سیستم مبتنی بر محاسبات است که در آن یک محدودیت میتواند روی فضای متغیرها تعریف شود. هدف این رویکرد یافتن مقادیر سازگار و مناسب برای متغیرها است بهطوری که این مقادیر محدودیتها را ارضا کنند و در دامنۀ متغیرها باشند. در مجموع، مزیت اصلی مدلهای برنامهریزی محدودیت نسبت به مدلسازی ریاضی، محدودهای از محدودیتهایی است که میتواند مستقیماً بیان شود (لئونگ[29]، 2004).
اولین ایدههای شکلگیری برنامهریزی محدودیت، از هوش مصنوعی نشأت میگیرد و مربوط به دهۀ شصت از قرن بیستم است. مزیت اصلی برنامهریزی محدودیت، جداسازی مدلسازی از جستجو برای راهحل است که به کاربر کمک میکند، تعریف شفافتری از محدودیتهای یک مسئلۀ خاص بیان کند. یکی از متخصصان مشهور بینالمللی بهنام فرویدر[30] بیان میکند که برنامهریزی محدودیت یکی از نزدیکترین مفاهیم در علوم کامپیوتر است که یک هدف عالی را برای برنامهنویسی دنبال میکند و آن هم این است که کاربر مسئله را بیان کند و کامپیوتر آن را حل کند (میلانو و والاس[31]، 2006)؛به بیان دیگر، پژوهشگران برنامهریزی محدودیت،الگوریتمها را از سایر رشتهها میگیرند و آنها را با روشهای جدید ترکیب میکنند و از الگوریتمهای پیچیده استفاده میکنند و هدف اصلی آنها ساخت سیستمی است که هر نوع مدل دقیق سطح بالا از مسئله را بگیرد و بهصورت اتوماتیک مدل را بهروشهای حل کارا تبدیل کند (چن و همکاران[32]، 2010).
برمبنای پژوهش ونهنتکریک و سراسوت[33](1997)، پایه و اساس برنامهریزی محدودیت در دو سطح قرار دارد:
1) سطح اول آنهایی هستند که تعریف کلی از سیستمهای محدودیتی ارائه میدهند.
2) دومین سطح زبان برنامهنویسی است که به کاربر اجازه میدهد که اطلاعات بیشتری را دربارۀ اینکه کدام محدودیتها باید تولید شوند و چگونه باید ترکیب و پردازش شوند مشخص میکنند. این زبانها صرفاً ازطریق عملیات ابتدایی با سطح اول در تعامل هستند و یک چارچوب کاملاً مشخصی برای ایجاد، دستکاری و تست محدودیتها ایجاد کرده و ویژگیهای اعلانی آنها را حفظ میکند.
بهطور کلی میتوان گفت برنامهریزی محدودیت از سه مرحله به پاسخ میرسد:
1)مدلسازی: فرمولهسازی مسئله بهصورت مجموعۀ محدودی از محدودیتها یا مسئلۀ ارضای محدودیت است؛
2)حل: حل مسئله ارضای محدودیت با زبانهای برنامهنویسی محدودیت است؛
3)نگاشت: نگاشت راهحل بهدستآمده برای مسئلۀ ارضای محدودیت به یک راهحل برای مسئلۀ اصلی است؛
در ادامه مسائل ارضای محدودیت برای درک بهتر راهحل برنامهریزی محدودیت شرح داده میشود.
1-3-3- مسائل ارضای محدودیت
بخش وسیعی از مسائل در حوزۀ هوش مصنوعی، مربوط به مسائل ارضای محدودیت است. مسائل ارضای محدودیت چارچوبی واحد برای مطالعۀ مسائل مختلف محاسباتی ارائه میکنند. مؤلفههای اصلی مسائل ارضای محدودیت، متغیرها و محدودیتها هستند. هدف اصلی در حل اینگونه مسائل، مقداردهی متغیرها است؛ بهگونهای که همۀ محدودیتهای تعریفشده در مسئله ارضا شوند. مقداردهی متغیرها با استفاده از دامنۀ تعریفشده روی آن متغیر صورت میگیرد؛ همچنین هنگام مقداردهی متغیرها باید توجه داشت که مقادیر همۀ متغیرها باید با هم سازگار باشند (ثانی و نمازی،1383).
یک مسئلۀ ارضای محدودیت بهصورت یک 3تایی تعریف میشود که X، یک مجموعۀ متناهی از متغیرها است و بهصورت است وDیک مجموعۀ متناهی از مقادیر دامنه است و بهصورتخواهد بود. همچنین Cمجموعۀ متناهی از محدودیتها است واست.
2-3-3- الگوریتمهای جستجو
حل مسائل ارضای محدودیت در هوش مصنوعی با کمک جستجو انجام میگیرد. فضای جستجوی این مسائل شامل وضعیتهایی است که در آنها مقدار تعدادی از متغیرهای موجود در مسئله تعیین شده است. منظور از وضعیت اولیه در این مسائل، تنها تعریف مسئله بدون مقداردهی به متغیرها است و نیز در وضعیت یا وضعیتهای هدف مقدار کلیۀ متغیرها با رعایت کلیۀ محدودیتها تعیین میشود (ثانی و نمازی،1383).
الگوریتمهای حل مسائل ارضای محدودیت میتوانند کامل یا ناکامل باشند. یک الگوریتم کامل یافتن جواب در صورت وجود را تضمین میکند و همچنین میتواند برای اثبات نبودِ جواب و یا یافتن یک جواب بهینۀ اثباتشده برای یک مسئلۀ ارضای محدودیت، بهکار گرفته شود (لئونگ، 2004).
یک مسئلۀ ارضای محدودیت را میتوان با استفاده از الگوی تولید-آزمایش ([34]GT) حل کرد، در این پارادایم، هر ترکیب ممکنی از متغیرها بهصورت سیستماتیک تولید شده و سپس آزمایش میشود که آیا همۀ محدودیتها را ارضا میکند یا خیر. اولین ترکیبی که همۀ محدودیتها را ارضا میکند، یک راهحل است. تعداد ترکیباتی که با این روش در نظر گرفته میشود برابر با ضرب دکارتی دامنۀ همۀ متغیرها است.یک روش کاراتر برای حل یک مسئلۀ ارضای محدودیت، الگوی عقبگرد ([35]BT) است. در این روش متغیرها بهترتیب مقداردهی میشوند و وقتی که متغیرهای مربوط به یک محدودیت مقداردهی شدند، اعتبار محدودیت بررسی میشود. اگر مقداردهی جزئی انجامشده، هرکدام از محدودیتها را نقض کند، یک عقبگرد به سمت آخرین متغیر که مقداردهی شده است و هنوز یک یا تعداد بیشتری مقدار برای جایگزینی دارد، انجام میشود. روش عقبگرد از جستجوی عمقاول[36]فضای راهحلهای بالقوۀ یک مسئلۀ ارضای محدودیت استفاده میکند (لئونگ، 2004). در این جستجو تمام فضای حالت بررسی میشود تا به جواب بهینه برسد. در جستجوی عمق اول ابتدا ریشۀ درخت و سپس همۀ فرزندانش ملاقات میشوند که عموماً فرزندان یک گره از چپ به راست ملاقات میشوند. در جستجو در عمق، یک مسیر آنقدر در عمق پیش میرود تا به بنبست برسد. در بنبست، دوباره آنقدر به عقب بر میگردد تا به یک گره با یک فرزند ملاقاتنشده برسد. سپس، از این فرزند ملاقاتنشده، پیشروی در عمق را مجدداً تا رسیدن به بنبست دیگر ادامه میدهد. روش عمقاول که بهعنوان روش جستجوی این پژوهش انتخاب شده است، در ردۀالگوریتمهای کامل قرار میگیرد و یک جواب بهینۀ اثباتشده میدهد (لئونگ، 2004).
4- مدل پیشنهادی
مدل پیشنهادی 3 گام دارد که در ادامه به تفصیل آمدهاند.
گام اول: قبل از فرمولهسازی مسئله، نخست لازم است مفروضات اولیه و همچنین محدودیتهای سخت و نرم مسئله که متناسب با نمونۀ موردمطالعه از تنوع بالایی برخوردار هستند، شناسایی شوند. مفروضات اولیه شامل تعداد استادان، رشتههای تحصیلی و ورودیهای موجود، تعداد اتاقهای موجود، روزهای کاری در هفته، بازههای زمانی و اوقات کاری صبح و عصر است. واژگان کاربردی استفادهشده در این پژوهش که شناسۀ فرضیات هستند، در جدول 1 آمده است. شناسایی این مفروضات ومحدودیتها از روشهای گوناگون نظیر بررسی دادههای گذشته، و مصاحبه با مسئولان برنامهریزی، امکانپذیر است.
گام دوم: در این گام، مدل بهصورت یک مسئلۀ ارضای محدودیت تعریف میشود؛ بهاین منظور لازم است متغیرهای تصمیمگیری و دامنههای مربوط به
هرکدام، معیّن شوند. در مدل پیشنهادی از دو نوع متغیر تصمیمگیری استفاده میشود: 1) متغیرهای تصمیمگیری اصلی که عبارت از زمان شروع هر درس، استاد آن درس و اتاق تخصیصیافته به آن درس هستند؛ و 2) متغیرهای تصمیمگیری کمکی که شامل زمان پایان هر درس و متغیرهای تصمیمگیری مربوط به تخطی از محدودیتهای نرم هستند.
گام سوم: درنهایت در گام پایانی، مسئله بهصورت یک مسئلۀ ارضای محدودیت فرمولهسازیشده و محدودیتهای سخت و نرم با توجه به متغیرهای تصمیمگیری اصلی و فرعیبیان می شوند.
1-4- محدودیتها
در گام نخست، اطلاعات بهدستآمده بهدلیل تنوع انتظارات و محدودیتهای دانشگاههای مختلف، خروجیهای متفاوتی بههمراه دارد؛ بنابراین آنچه که در ادامه ملاحظه میشود، محدودیتهای استخراجشده از مطالعۀ موردی این پژوهش است.محدودیتهای سخت و نرم مسئله ازطریق بررسی دادههای گذشته و مصاحبه با مسئولان مربوطه شناسایی شد که در ادامه بهتفکیک بیان میشوند.
گفتنی است که محدودیتهای سخت در میان تمام جدولهای زمانبندی دروس دانشگاهی مشترک است؛ ولی محدودیتهای نرم بسته به مطالعۀ کاربردی موردنظر، طیفی از محدودیتهای متنوعی را در بر میگیرد.
جدول (1): واژگان کاربردی تعریف مسئلۀ جدول زمانبندی
|
گروه آموزشی: موجودیتیاست که با سه خصیصۀ مقطع، نام رشته و سال ورود مشخص میشود؛ برای مثال کارشناسی بازرگانی 91 مربوط به دانشجویان کارشناسی رشته بازرگانی ورودی سال 1391است. جلسه: تعداد جلسات یک درس، متناسب با تعداد واحدهای تعریفشده برای آن، بیان میشود. دروس 1 و 2 واحدی در یک جلسه در هفته برگزار میشوند و برای دروس سه واحدی دو جلسه در هفته تعریف میشود. واحد درسی: هر درس از تعدادی واحد تشکیل شده که تعداد جلسات هر درس را نیز مشخص میکند. استاد: شخصی که تدریس درسی را بر عهده دارد. استاد میتواند عضو هیئت علمی گروه موردمطالعه باشد و یا از گروههای درسی دیگر موجود در دانشگاه برای تدریس درسی خاص، معرفی شده باشند. به هر استاد مجموعهای از دروس که در تخصص وی است، تخصیص داده میشود. دروس سرویسی: دروسی که توسط گروههای آموزشی دیگر برای دانشجویان گروه آموزشی موردمطالعه، ارائه میشود. روزهای کاری: روزهایی که دانشجویان به تحصیل میپردازند. بازۀ زمانی: یک بازۀ زمانی معرف یک ساعت کاری مشخصی از یک روز معین است. بازههای زمانی متداخل: دو بازۀ زمانی برای دو درس متفاوت، هنگامی تداخل پیدا میکنند که ساعت شروع یکسانی داشته باشند. |
1-1-4- محدودیتهای سخت
محدودیتهای سخت این مسئله به شرح زیر هستند:
- برگزارنشدن دروس در غیر روز کاری؛
- محدودیت تعداد اتاقها؛
- اختصاصندادن بیش از یک درس بهطور همزمان به هر استاد؛
- برگزارنشدن دو درس متفاوت در یک اتاق در هر زمان؛
- تداخلنداشتن زمان دروس یک رشتۀ خاص؛
- یکسانبودن جلسات مختلف یک درس براییک ورودی خاص؛
- دروس سرویسی تنها در ساعات مشخصشده ارائه شوند؛
- برگزاری دروس در اتاق با ظرفیت مناسب؛
- جلسات یک درس خاص، در یک روز برگزار نشوند؛
- درنظرگرفتن کمینه ساعات تدریسی استادان در طول هفته؛
- جلسات دوساعتی در ساعات زوج اوقات کاری هر روز شروع شوند. منظور از ساعات زوج، ساعات 8، 10، 14 و 16 یک روز کاریاست؛
- دروسدر ساعات حضورنداشتن استادان برگزار نشوند.
2-1-4- محدودیتهای نرم
محدودیتهای نرم اینمسئله به دو دستۀ محدودیتهای نرم سطح یک و دو دستهبندیمیشوند. محدودیتهای نرمسطح یک، شامل محدودیتهای آموزشی و محدودیتهای نرم سطح دو شامل انتظارات استادان و دانشجویان است. این دو دسته محدودیت به شرح زیر هستند:
الف) محدودیتهای آموزشی:
- اتاق بتواند امکانات خاص یک درس را پشتیبانی کند؛
- بیشینه ساعات تدریسی استادان در طول هفتهدر نظر گرفته شود؛
- روزهای تشکیل دروس دانشجویان ارشد و دکتری متوالی باشند؛
-فاصلۀ (شکاف) میان دروس یک ورودی در یک روز کاری، کم باشد.
ب) انتظارات:
- تا جایی که امکانپذیر است، ساعات ترجیحی استادان برای برگزاری دروس در نظر گرفته شوند؛
- درنظرگرفتن دانشجو(یان) در یک ورودی خاص که بهدلیل مشکلات فیزیکی ترجیح میدهند دروس آنها در طبقۀ اول باشد.
2-4- پیادهسازی مدل پیشنهادی
در این گام، متغیرهای تصمیمگیری تعیین شده و محدودیتهای سخت و نرم براساس این متغیرها تعریف میشوند. پارامترهای تعریف در جدول 2 آمدهاند. مدل پیشنهادی شامل مجموعۀ برنامه درسی P={p1, p2,…, pn}است. برای دروس با تعداد واحد بیشتر از 2 که نیاز به برگزاری بیش از دو جلسه در هفته دارند، دو موجودیت با IDیکسان تعریف میشود. از آنجایی که یک مسئلۀ ارضای محدودیت با متغیرهای تصمیمگیری بههمراه مقادیر دامنۀآنها و همچنین محدودیتهای اعمالشده برآنها تعریف میشود، میتوان مسئلۀ جدول زمانبندی دروس دانشگاهی را بهمسئلۀ ارضای محدودیت تبدیل کرد. این فرایند بهترتیب از تعریف متغیرهای تصمیمگیری آغاز می شود و به بیان تمامی محدودیتهای موجود میپردازد. درنهایت هدف مدل، ارضای کامل محدودیتهای سخت و حداقلسازی میزان تخطی از محدودیتهای نرم است.
1-2-4- متغیرهای تصمیمگیری
متغیرهای تصمیمگیری جهت پیادهسازی این مسئله به دو دستۀمتغیرهای اصلی و کمکی تقسیم میشوند. متغیرهای اصلی و دامنۀ مقادیر آنها که بر روی اعضای مجموعۀpتعریف میشوند، به شرح زیر هستند:
: زمان شروع موجودیتاست که دامنهآن شامل مقادیر مجموعهTSاست.
: اتاق تخصیصیافته به موجودیتاستکه دامنۀ آن شامل مقادیر مجموعۀRاست.
: استاد تخصیصیافته به موجودیتاست که دامنۀ آن شامل مقادیر مجموعۀTاست.
متغیرهای کمکی نیز به شرح زیر هستند:
: زمان پایان موجودیتاست که دامنهآن شامل مقادیر مجموعۀTSاست.
: جریمۀ تخصیصیافته به موجودیت که بهدلیل نقض محدودیت نرماتفاق میافتد.
2-2-4- پیادهسازی محدودیتها
غالبأ در محدودیتها از عبارات منطقی استفاده شده است. این عبارات بهخصوص در محدودیتهای نرم، سبب بهبود خوانایی برنامهنویسی مدل و ارتقای کارایی اجراگرفتن از آن شده است. منظور از یک فرمان منطقی این است که یک عبارت در صورت صحیحبودن، مقدار 1 و در صورت اشتباهبودن، مقدارصفر را به خود میگیرد؛ برای مثال عبارت فرمان منطقی بهصورت زیر توصیف میشود:
1-2-2-4- پیادهسازی محدودیتهای سخت
بهدلیل تعریف مناسب دامنۀ متغیرهای تصمیمگیری، دروس تنها در ساعات کاری و همچنین روزهای کاری هفته تشکیل میشود. همچنین تشکیل این دروس نیز در اتاقهای موجود صورت میپذیرد. در نتیجه این سه محدودیت سخت ذاتاً ارضا میشوند.
سایر محدودیتهای سخت مسئله با درنظرگرفتن متغیرهای تصمیمگیری به شرح زیر هستند:
- درس پس از شروع در طی زمان تخصیصیافته به آن پایان یابد. در این محدودیت متغیر کمکی محاسبه میشود؛
(1)
- استاد باید بتواند درس را تدریس کند (درس در تخصص وی باشد).
(2)
- استاد نمیتواند در یک زمان خاص بیش از یک درس را تدریس کند.
(3)
- در یک اتاق خاص، همزمان بیش از یک درس، تدریس نشود؛
(4)
جدول (2): پارامترهای مسئله
|
P={p1, p2,…, pn}: مجموعۀ موجودیتهای برنامه است که هر عضو، یک چندتایی را شامل میشود. gمعرف رشته، cمعرف درس، dمعرف طول زمان جلسه و IDشماره درس است. i: شناسۀ برنامۀiام. ci: شناسۀ درس cاز برنامۀام. : مدتزمان جلسۀ درس cاز برنامۀام. : استاد اختصاصیافته به درس cاز برنامۀام. : مجموعۀ استادان. : مجموعۀ ورودیهای مختلف که هر موجودیتشامل چندتایی است که neنام ورودی و puتعداد دانشجویان آن ورودی است. : مجموعۀ موجودیت ورودیهای کارشناسی. : مجموعۀ ورودیهای کارشناسی ارشد و دکترا. : مجموعۀ دروس. : مجموعۀ بازههای زمانی. : مجموعۀ بازههای زمانی که با ساعات زوج آغاز میشوند. : مجموعۀ محدودیتهای نرم. : مجموعۀ دروسی که استاد tقادر به تدریس آنهاست. : مجموعۀ استاد که قادر به تدریس درس cهستند. : مجموعۀ موجودیت اتاقهای دردسترس است که هر موجودیت چندتایی را شامل میشود. nrنام اتاق و fطبقهایاست که اتاق در آن قرار دارد. ظرفیت کلاس نیز با capمشخص میشود. : مجموعۀ اتاقهایی که میتوانند امکانات موردنیاز درس cرا برآورده سازند. : مجموعۀ موجودیتهای دروس سرویسی است که هر موجودیت چندتایی را شامل میشود. cنام درس و srزمان شروع تخصیصیافته به آن درس است. Mday: تعداد بازههای زمانی صبح Eday: تعداد بازههای زمانی عصر EM: کل بازههای زمانی یک روز : مجموعۀ موجودیتهای ساعات حضورنداشتن استادان است که هر موجودیت شامل چندتاییاست. asبازههای زمانی حضورنداشتن استادان است. : مجموعۀ موجودیتهای ساعات ترجیحی استادان است که هر موجودیت است. psبازههای زمانی ترجیحی استادان است. : مجموعۀ موجودیتهای سابقۀ استادان است که هر موجودیت است. repسابقۀ استادان است. : مجموعۀ موجودیتهای حداکثر ساعات تدریس استادان در هفته است که هر موجودیت شامل چندتایی است. maبیشینه ساعت کاری استادان در هفته است. : مجموعۀ موجودیتهای حداقل ساعات تدریس استادان در هفته است که هر موجودیت شامل چندتاییاست. miکمینه ساعت کاری استادان در هفته است. : ضریب تخطی تعریفشده برای محدودیت نرم . |
- دروس مربوط به یک رشتۀ خاص، ازنظر زمانی تداخل نداشته باشند؛ به معنی دیگر، در یک زمان خاص، برای دانشجویان یک رشته، بیش از یک درس تشکیل نشود.
(5)
- جلسات مختلف یک درس یکسان برای یک رشتۀ خاص، توسط یک استاد یکسان تدریس شود.
(6)
- دروس سرویسی تنها در ساعات مشخصشده، برگزار شوند.
(7)
- ظرفیت اتاق مناسب با تعداد دانشجویان حضوریافته در آن باشد.
(8)
- جلسات یک درس یکسان از یک رشتۀ خاص، در یک روز برگزار نشوند.(9)
- ساعات کاری استادان کمتر از حداقل ساعات تعیینشده نباشد.
(10)
- جلسات دو واحدی در اوقات کاری زوج شروع شوند.
(11)
- دروس در ساعات حضورنداشتن استادان برگزار نشوند.
(12)
2-2-2-4- پیادهسازی محدودیتهای نرم
محدودیتهای نرم مسئله به دو دستۀ محدودیتهای آموزشی و انتظارات تقسیم میشوند. این محدودیتها با درنظرگرفتن متغیرهای تصمیمگیری به شرح زیر هستند.
الف) محدودیتهای آموزشی:
- اتاق بتواند امکانات خاص یک درس را پشتیبانی کند.
(13)
- ساعات کاری استادان از بیشینه تعیین شده تجاوز نکند.
(14)
- بین روزهای تشکیل دروس دانشجویان ارشد و دکترا فاصلهای نباشد. (ترجیحاً در 2 یا 3 روز برگزار شوند.)
(15)
فاصلۀ (شکاف) میان دروس یک ورودی در یک روز کاری کاهش پیدا کند. در این محدودیت فاصله زمان شروع یک درس از خاتمۀ درس قبلی مربوط به یک ورودی یکسان، باید کمتر از 3 واحد زمانی باشد.
(16)
ب) انتظارات:
- تا جایی که امکانپذیر است، ساعات ترجیحی استادان برای برگزاری دروس در نظر گرفته شوند.
(17)
در این محدودیت ضریب سابقۀاستادان نیز در نظر گرفته میشود. یعنی راهحل مسئله بهگونهای است که ساعات ترجیحی استادان باسابقه در اولویت این محدودیت قرار گرفته است.
- درنظرگرفتن دانشجو(یان) در یک ورودی خاص که بهدلیل مشکلات فیزیکی ترجیح میدهند دروس آنها در طبقۀ اول باشد.
(18)
در مدل پیشنهادی، هدف ارضای کامل محدودیتهای سخت و همچنین ارضای حداکثری محدودیتهای نرم است؛ بنابراین تابع هدفی بهمنظور حداقلکردن جریمههای اختصاصیافته به تخطی از محدودیتهای نرم، تعریف میشود.
(19)
(20)
(21)
(22)
(23)
(24)
ضرایب تابع هدف هستند. این ضرایب بهمفهوم اهمیت یک محدودیت است. این ضرایبدر مطالعۀ موردی ازطریق مقایسههای زوجی و استفاده از تکنیکAHPبهدست میآید. مقایسههای زوجیبراساس نظر کارشناسان است.
5- مطالعۀ موردی
در این بخش، مدل پیشنهادی برای ایجاد جدول زمانبندی گروه مدیریت دانشگاه اصفهان در ترم نخست سال تحصیلی 94-1393 پیادهسازی میشود. در این گروه در ترم نخست سال تحصیلی 94-1393 تعداد 24 عضو هیئت علمی مشغول به تدریس هستند. روزهای کاری دانشگاه اصفهان از شنبه تا چهارشنبهاست. تعداد ساعات کاری یک روز در دانشگاه اصفهان نیز 9 ساعت است. درنتیجه تعداد کل بازههای زمانی 9×5 است. در مدل پیشنهادی بازههای زمانی مجموعۀ {45،...1،2}T= را تشکیل میدهد؛ مثلاً بازۀ زمانی 12، نمایانگر ساعت 11 تا 12 روز یکشنبه است. اوقات کاری صبح دربرگیرندۀ بازههای زمانی موجود در بین ساعت 8 صبح تا 12 ظهر (شامل 4 بازۀ زمانی) است و اوقات کاری عصر دربرگیرندۀ بازههای زمانی موجود در بین ساعت 13 بعدازظهر تا18 عصر (شامل 5 بازۀ زمانی) است. مجموع کل دروس تدریسی در سه مقطع این گروه برابر146 است که در 36 اتاق تدریس میشوند. دانشجویان این دانشکده در سه مقطع کارشناسی، کارشناسی ارشد و دکترا و در مجموع در 31 گروه آموزشی مشغول به تحصیل هستند. ساختمان مجموعۀ کلاسهایی که اتاقها در آن استقرار دارند، شامل 2 طبقه است. سایر اطلاعات موردنیاز برای حل مسئله که شامل سابقۀاستادان، ساعات ترجیحی و حضورنداشتنآنها، بیشینه و کمینۀ کاری آنها در طول یک هفتۀ کاری و دروس سرویسی هستند، ازطریق مصاحبه با مسئولین برنامهریزی گروه مدیریت دانشگاه اصفهان، بهدست آمد. سپس با تعریف متغیرهای تصمیمگیری و شناسایی محدودیتها مسئله بهصورت یک مدل برنامهریزی محدودیت تعریف شد. مدل بهدستآمده در نرمافزار IBM ILOG CPLEXو با زبان برنامهنویسی OPLپیادهسازی شد.
6- ارزیابی نتایج
مسئلۀ جدول زمانبندی دروس دانشگاهی در گروه مدیریت دانشگاه اصفهان، با دادههای اصلی و درنظرگرفتن تمام محدودیتها، با 1100 متغیر تصمیمگیری و تعداد 2،838،188 محدودیت در مدتزمان 1315 ثانیه حل شد. الگوریتمجستجوی مورداستفاده در این پژوهش، الگوریتمجستجوی عمقاول و راهاندازی مجدداست.
در جدول 3 تأثیر اضافهکردن محدودیتهای نرم به مسئله، در زمان حل و همچنین تعداد موجودیتهایی که به آنهاجریمه تخصیص داده شده آمده است. ستون نخست شامل نام محدودیت نرم جدید اضافهشده به محدودیتهای نرم قبل، است و ستون دوم تعداد تخطی از این جریمههااست و درنهایت ستون سوم نیز نمایانگر زمان رسیدن به جواب مسئلهاست. همانطور که در این جدول مشاهده میشود، برنامۀ نهایی بهدستآمده با درنظرگرفتن تمام محدودیتها، تنها در 2 مورد تخطی داشته است. از طرفی اضافهکردن محدودیتهای نرم، زمان حل را افزایش دادهاند. البته درنهایت زمان کل حل مسئله در مقایسه با وقتی که کارشناسان برنامهریزی برای تهیۀ برنامۀ آموزشی صرف میکنند، بسیار ناچیز است.
جدول (3):تأثیر افزودن محدودیت نرم بر جواب و زمان حل مسئله
|
محدودیت نرم |
تعداد تخطی |
زمان (ثانیه) |
|
- |
- |
7/224 |
|
(12) |
0 |
6/318 |
|
(15) |
0 |
2/1232 |
|
(16) |
0 |
7/1240 |
|
(18) |
0 |
4/1260 |
|
تمام محدودیتها |
2 |
1315 |
الگوریتمجستجوی مورداستفاده در این پژوهش (عمق اول)، در طی زمان رسیدن به بهترین جواب، راهحلهای موجه مختلفی ارائه میدهند. آخرین راهحل بهترین جوابی است که توانسته تا حدود بسیار
زیادی محدودیت های نرم مسئله را ارضا کند.در نمودار 1 مراحل رسیدن به یک جواب با حداقل تخظی از تابع هدف را برای جواب نهایی مسئلهنمایشداده میشود.در فرایند حل، تعداد جوابهای
موجه برابر 34 است که درنهایت با تعداد 2 واحد تخطی از محدودیتهای نرم، در 1315 ثانیه به جواب نهاییمیرسد.این جواب از آنجاییکه توسط یک الگوریتم کامل بهدست آمده است، یک جواب بهنیه است.
شکل 1. جوابهای مختلف حل مسئلۀ نهایی
در جدول 4 نمونهای از برنامه درسی ترم هفتم گروه مدیریت صنعتی دانشگاه اصفهان در نیمسال نخست سال تحصیلی 94-1393 مشاهده میشود.
خواستههای شناساییشده برای این برنامه به شرح زیر هستند:
- درس دانش خانواده در ساعت 16-14 روز شنبه تدریس شود؛
- درس مدیریت در ساعت 16-14 روز چهارشنبه توسط خانم دکتر ص تدریس شود.؛
- دکتر «ق»در کل روز شنبه و همچنین روز سهشنبه ساعت 10-8 صبح کلاس نداشته باشد؛
- دکتر «ع» در ساعت 12-10 دوشنبه کلاس نداشته باشد؛
- کلاسهای دکتر«ع» ترجیحا در اوقات کاری صبح برگزار شود؛
- دکتر «ش» در روز چهارشنبه و همچنین ساعت 10-8 روز سه شنبه کلاس نداشته باشد.
در این برنامۀ درسی، محدویتهای سخت کاملاً ارضا شده و خواستهها و انتظارات نیز برآورده شدهاند. علاوه بر رعایت تداخلنداشتن زمانی و مکانی، شروع جلسات دو ساعتی در ساعات زوج اتفاق افتاده و دروس سرویسی نیز در ساعات خواستهشده قرار گرفته است. از طرفی حداقل شکاف در دروس روزانۀ دانشجویان ملاحظه شده است. این امر در راستای بهبود شرایط آموزش و استفاده مناسب از وقت دانشجویان، امری ضروری به نظر میآید. خواستههای استادان نیز در این برنامه کاملاً رعایت شدهاند.
7- نتیجهگیری
در این مقاله، مدل برنامهریزی محدودیت برای حل مسئله جدول زمانبندی دروس دانشگاهی بهکار گرفته شد. محدودیتهای شناساییشده برای حل اینمسئلهنیز به دو دستۀ محدودیتهای سخت و نرم تقسیمبندی شد. برای حل اینمسئله باید توجه داشت که گرچه محدودیتهای سخت برای اکثر دانشگاههایکساناست، محدودیتهای نرم بسته به محیط تعریفشده برای انجام پژوهش متفاوت است؛ زیرا انتظارات ذینفعان (شامل استادان، دانشجویان و مسئولین برنامهریزی) در دانشگاههای مختلف، متفاوت است. درنتیجه نخستین گام در جهت پیادهسازی مدل، شناسایی این محدودیتهااست. این محدودیتهاو انتظارات در مطالعۀ موردی، ازطریقبررسیدادههای گذشته و همچنینمصاحبۀ باز با مسئولین برنامهریزی شناساییشدند.
مهمترین تفاوت این پژوهش با سایر پژوهشها، تمرکز بر محدودیتهای نرم است. محدودیتهای سخت که ارضایآنها ضروریاست، در جهت موجهبودن برنامۀ بهدستآمده، اعمال میشود؛ لکن محدودیتهای نرم در جهت ارضای حداکثری انتظارات ذینفعانمسئله اعمال میشود. راهکار پیشنهادی، تخصیص جریمه به تخطی از محدودیتهای نرم و حداقلسازی این جریمههااست.در مدلهایی که از برنامهریزی محدودیت برای حل مسئله استفاده شده است، از محدودیتهای وزندار استفاده کردهاند. درنتیجه به محدودیت و نه موجودیتهای درون هر محدودیتاولویت داده میشود. این رویکرد گرچه سبب کاهش تعداد محدودیتها میشود، کیفیت برنامه را پایین میآورد؛ مثلاً اگر استادی درخواست دارد که دروس وی در روزهای فرد برگزار شوند، در صورتی که تمام دروس را یک موجودیت در نظر بگیریم (همانگونه که در مدلهای پیشین بوده است) در پایان ممکن است اگر بهدلیل اختصاص جریمه به آن استاد، خواستهاش برآورده نشود، تمام دروس در روزهایزوج برگزار شوند. در صورتیکه در مدل پیشنهادی با وزندارکردن تکتک دروس هر استاد، تا جایی که امکان دارد دروس وی در روزهای فرد برگزار میشوند و در صورت تخصیص جریمه، تعداد خاصی از آن دروس، در روزهایزوج برگزار میشوند. مدل پیشنهادی با تخصیص جریمه، موجودیتهای درون یک محدودیت را نیز وزندار کرده است.
برای حل مدل پیشنهادی، متغیرهای تصمیمگیری بر روی دامنههای خود تعریف شده و محدودیتها نیزمشخص میشوند. پس از تعریف متغیرهای تصمیمگیری، محدویتهای سخت و نرم براساس این متغیرها پیادهسازی میشوند.
درنظرگرفتن جریمه برای تمامی موجودیتهایی که به محدودیتهای نرم تخصیص داده میشوند، سبب افزایش تعداد محدودیتهایی میشود که در هنگام اجرای مدل، باید در نظر گرفته شوند؛ مثلاً در مطالعۀ موردی اینپژوهش، پس از حل مدل توسط نرمافزار IBM ILOG CPLEX تعداد محدودیتهای حلشدۀ درنظرگرفتهشده نزدیک به 3 میلیون عدد برآورد شدهاست. حل این تعداد محدودیت، تنها در مدل برنامهریزی محدودیت امکانپذیر است. مدل پیشنهادی برای مطالعۀ کاربردی این پژوهش در مدتزمان کمتر از 20 دقیقه به جواب میرسد که نسبت به تعداد محدودیتهایمسئله، بسیار مناسباست. البته باید در نظر گرفت که تابع هدف در برای حداقلسازیجریمهها عمل میکند، درنتیجه ممکن است بهدلیل تضاد در محدودیتها، این مقدار به صفر نرسد؛ اما در مناسبترین مقدار خود قرار میگیرد و این نقطه همانمطلوبیت حداکثری خروجیاست که لزومأ برطرفکنندۀ صددرصدی محدودیتهای نرم نیست، ولی رضایت حداکثری از برنامه را حاصل میکند.
از جمله محدودیتهای فنی مسئله، عدم بهاصطلاح سفارشیسازی الگوریتم جستجوی انتخابی برای حل مسئلهاست. از آنجاییکه زمان رسیدن به جواب بهینه در مدلهای CP، ارتباط مستقیمی با الگوریتم حل آن دارد، سفارشیسازی الگوریتم جستجو با راههایی نظیر تخصیص مقادیر اولیه به متغیرها و یا تقویت انتشار محدودیت، میتوان در زمان بسیار مناسبتری به جواب بهینه رسید.
جدول (4): برنامۀ هفتگی ترم هفتم مدیریت صنعتی با درنظرگرفتن تمام محدودیتها
|
|
شنبه |
یک شنبه |
دوشنبه |
سه شنبه |
چهارشنبه |
|
9-8 |
دانش خانواده سرویسی |
|
|
|
|
|
9-10 |
|
|
|
|
|
|
11-10 |
کنترل پروژه دکتر ع 5-710
|
مدیریت کارخانه دکتر ع 16-711
|
|
|
مدیریت کارخانه دکتر ع 15-711 |
|
12-11 |
|
|
کنترل پروژه دکتر ع 1-710 |
||
|
14-13 |
|
||||
|
15-14 |
|
طرح ریزی سیستمها دکتر ک 17-711 |
مدیریت مواد دکتر ق 23-710
|
طرح ریزی سیستمها دکتر ک 25-710
|
مدیریت دکتر ص 2-710
|
|
16-15 |
|
||||
|
17-16 |
|
مدیریت ایمنی دکتر ک 1-710 |
بهره وری دکتر ش 4-710
|
|
|
|
18-17 |
|
||||
8- پیشنهادهای آینده
با درنظرداشتن پیشنهادهای زیر و اعمال آنها، میزان رضایتمندی از خروجی مدل پیشنهادی را میتوان افزایش داد. مدل پیشنهادی بعد از فرایند تخصیص برنامۀ درسی دانشجویان، به حل مسئله میپردازد؛ میتوان با یک دید کلی، فرایند تعیین دروسی را که یک دانشجو در هر ترم بایدبگیرد نیز به گامهای مدل اضافه کرد تا مدلییکپارچه بهدست آید. در این پژوهش هدف، دستیابی به یک جواب رضایتبخش است و الگوریتمهای مورداستفاده برایجستجو، تنها به اولعمق محدود شده است. میتوان الگوریتمهایجستجوی مختلف را برای پیداکردن راهحل بهینه،
امتحان کرد. از طرفی میتوان با سفارشیسازیاین الگوریتمها، سرعت رسیدن به جواب بهینه را افزایش داد.میتوانبا اجرای مدل برای جدول زمانبندی برنامۀ آموزشی تمام گروهها، محدودیتها و انتظارات جدید را شناسایی کرد و با درنظرگرفتن تمامی این خواستهها مدلی پیشنهاد داد که خروجی آن با درنظرگرفتن این خواستهها، بتواند در جهت ارتقای سطح علمی دانشجویان و همچنین افزایش بازده استادان حرکت کند. استفاده از مدلهای چندمرحلهای نیز در تسریع حل مسئله مؤثر هستند. میتوان مدل دومرحلهای طراحی کرد که در مرحلۀ نخست، دروس را به استادان تخصیص دهد و سپس در مرحلۀ دوم برای این دروس تخصیص داده شده، زمانبندی را اعمال کند.
)