بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
يک مدل برنامه ريزي عدد صحيح براي حل مسأله زمان بندي دانشگاهي: مطالعه موردي
چکيده
مسأله زمان بندي دانشگاهي به صورت فرآيند تخصيص يک تعداد رويداد هم چون سخنرانيها، جلسات و... به يک تعداد محدود بازه زماني (و کلاس ) در ارتباط با يک سري محدوديت ها تعريف ميشود. در اين مقاله يک مدل برنامه ريزي عدد صحيح با متغيرهاي صفر-يک براي حل مسأله زمان بندي ترم دانشگاهي ارائه شده است . اين مدل قوانين آموزشي برخي دانشگاه ها را در نظر ميگيرد که در آن ها بعضي از کلاس ها به صورت هفته در ميان برگزار ميشود. در اين مدل سعي شده است علاوه بر موسسه و اساتيد تمايلات دانشجويان را نيز در نظر بگيرد. تابع هدف خطي اين مدل سعي دارد علاوه بر رعايت قوانين آموزشي و ارائه يک جدول زمان بندي موجه ، تمايلات موسسه ، اساتيد و دانشجويان را تا حد ممکن برآورده سازد. در نهايت به منظور اعتبارسنجي مدل ، براي گروه مهندسي صنايع دانشگاه سجاد پياده سازي شده است .
کلمات کليدي
مسأله زمان بندي، زمان بندي ترم دانشگاهي، بازه هاي زماني، برنامه ريزي عددصحيح ، متغيرهاي صفرويک ، بسته هاي زماني .
١- مقدمه
هدف تمامي مسائل زمان بندي تخصيص يک سري رويداد (هم - چون وظايف ، رويدادهاي اجتماعي، وسايل نقليه يا افراد) به تعداد محدودي منبع در طول زمان است . يکي از مهم ترين و تکراريترين اين مسائل ، مسائل زمان بندي آموزشي است که عموما براي بالا بردن بار آموزشي و افزايش بهره وري آموزش بکار مي روند. مسائل زمان بندي آموزشي نيز به دو دسته کلي تقسيم مي شوند: زمان بندي امتحانات دانشگاهي و زمان بندي ترم دانشگاهي . زمان بندي مدرسه اي نيز حالت خاصي از مسأله زمان بندي ترم دانشگاهي است . در ادامه تعريفي از اين مسائل ارائه ميشود[٦]:
زمان بندي امتحانات دانشگاهي: اغلب موسسات آموزشي در انتهاي هر ترم يا سال نياز به زمان بندي يک سري امتحانات دارند. در ساده ترين شکل ، مسأله به صورت تخصيص يک سري امتحانات به يک تعداد خاص بازه هاي زماني تعريف ميشود به گونه اي که هيچ دانشجويي در يک بازه زماني بيش از يک امتحان نداشته باشد.
زمان بندي ترم دانشگاهي: زمان بندي ترم شامل شرايطي است که دانشجويان نياز به يک سري درس (سمينار، آزمايشگاه ) دارند و هدف حداقل کردن تعداد کل برخوردها و ارضاء همه ي محدوديت هايي است که دانشگاه موردنظر اعمال نموده است .
تفاوت هاي زمان بندي ترم دانشگاهي و زمان بندي امتحانات دانشگاهي به صورت خلاصه در جدول ١ آمده است . در بين تحقيقات انجام شده بيشتر به زمان بندي ترم دانشگاهي پرداخته شده ، از مقالاتي که براي حل مسأله زمان بندي امتحانات منتشر شده است ميتوان به [٢] و [٣] اشاره کرد.
از طرفي در دانشگاه الزامي براي يک زمان بندي پيوسته و پشت سر هم وجود ندارد، در صورتي که براي زمان بندي مدرسه اي چنين است ، در زمان بندي مدرسه اي براي هر گروه دانش آموز که در يک کلاس ثبت نام کرده اند برنامه اي از دروس به صورت پشت سرهم ارائه ميشود، از طرفي در زمان بندي مدرسه اي انتخاب دروس براي دانش آموزان به صورت اجباري است و همچنين برنامه زمان بندي
براي تمام اعضاي يک کلاس يکسان خواهد بود. روش هاي کلي ارائه شده براي حل مسأله زمان بندي ترم دانشگاهي براي زمان بندي مدرسه اي نيز با اندکي تغيير قابل استفاده است .
مدل ارائه شده در اين مقاله داراي خصوصيات منحصربفردي ميباشد که از آن جمله در نظر گرفتن گروهاي دانشجويي و سلايق و مطلوبيت آنها، کلاس هاي هفته درميان و در نظرگرفتن بسته هاي زماني براي بهبود برنامه ي درسي اساتيد و دانشجويان است . در ادامه - ي مقاله در بخش دو مرور ادبيات ارائه خواهد شد و در بخش سه مدل رياضي ارائه ميشود و در بخش چهارم به مطالعه موردي اشاره کوتاهي خواهد شد.
٢- مرور ادبيات
استفاده از برنامه ريزي عددصحيح (بعضاً برنامه ريزي خطي عدد صحيح ) براي حل اين مسأله به گونه هاي مختلفي انجام شده است .
البته معمولا مدل سازي ها به گونه اي است که در دسته برنامه ريزي عددصحيح مختلط قرار ميگيرد، در بعضي موارد از برنامه ريزي آرماني استفاده ميشود و در بسياري از مدل ها در واقع از برنامه ريزي خطي عددصحيح استفاده شده است . در سال ١٩٩٧ بدري و همکاران با به کار گيري برنامه ريزي آرماني، يک مدل چندهدفه را براي زمان بندي دانشگاهي ارائه نمودند.[٩] از محققيني که در اين زمينه کار کرده اند و مقاله و مدل آنها بسيار مورد توجه بوده است داسکالکي و بيرباس هستند که دو مقاله در سال هاي ٢٠٠٤ و ٢٠٠٥ منتشر کرده اند[٧] و [ ٨] همچنين در سال ٢٠٠٦ ميرحسني مدلي را براي زمان بندي دانشگاهي ارائه کرده است [١٠] در سال ٢٠٠٦ يک برنامه ريزي رياضي نيز براي زمان بندي دانشگاهي توسط ياکوب و همکاران ارائه شد. همچنين فراهاني و حاجي يخچالي در [١] يک مدل برنامه ريزي عدد صحيح مشابه مدل داسکالکي ارائه دادند.
٣- ارائه يک مدل برنامه ريزي عددصحيح
برنامه ريزي عددصحيح بارها براي حل مسأله زمان بندي استفاده شده و توسط روش هاي دقيق و يا ابتکاري آن را حل نموده اند. [١] و [٧] و [٨] در اين بخش به ارائه ي يک مدل برنامه ريزي عدد صحيح خواهيم پرداخت . مدلي که گسترش پيدا خواهد کرد با توجه به قوانين و مقررات موسسه آموزش عالي سجاد تبيين خواهد شد. مدل ارائه شده داراي خصوصيات منحصر بفردي است که در بخش بعدي بدان اشاره خواهد شد.
٣-١- تعريف مسأله
در اين مسأله کلاس هاي هفته درميان را –مطابق قوانين آموزشي موسسه آموزش عالي سجاد و ديگر موسسات - در نظر گرفته ايم که از هر دو هفته يک بار تشکيل ميشود. براي گنجاندن اين کلاس ها در مدل ، بايد فرضيات را به گونه اي تغيير داده و متغير تصميم اصلي را به گونه اي تعريف نماييم که امکان ايجاد محدوديت هاي مورد نظر و گرفتن جواب صحيح باشد. بدين منظور ما نيم بازه ها را تعريف مي - کنيم ، يعني هر بازه زماني را به دو قسمت تقسيم ميکنيم . کلاس هاي دائمي (هر هفته ) در هر دو نيم بازه و کلاس هاي هفته درميان در يکي از نيم بازه ها تشکيل ميشود. بدين ترتيب ما جدول زمان بندي را به گونه - اي جدول زمان بندي ديگر تبديل کرديم که نشان دهنده برنامه هر هفته است . پس با اين تبديل مسأله را حل کرده و در انتها جدول زمان بندي حاصل را به حالت اوليه باز ميگردانيم .
در اين مدل ما دانشجويان را به صورت گروه هاي دانشجويي در نظر ميگيريم که هر گروه دانشجويي برنامه ي مشابهي دارند، گروه هاي دانشجويي ميتوانند از طريق پيش ثبت نام و يا نظرسنجي اوليه تشکيل شوند.
همچنين براي بهبود جواب و ايجاد برنامه هاي مناسب براي اساتيد و دانشجويان مفهومي به نام بسته هاي زماني را معرفي کرده ايم . بسته هاي زماني از چند بازه زماني تشکيل شده است که استاد (و يا گروه دانشجويي) ترجيح ميدهد يا در اين بسته زماني کلاس نداشته باشد و يا اگر کلاس دارد از يک تعدادي بيشتر کلاس داشته باشد. )به عنوان مثال ميتوانيم يک بسته زماني را صبح هر روز و بسته زماني ديگر را عصر هر روز معرفي کنيم .)
در ادامه به مدل سازي رياضي مسأله ميپردازيم ، در ابتدا متغيرها و پارامترها و مجموعه ها تعريف ميشوند، بعد از آن تابع هدف معرفي شده و سپس محدوديت هاي مختلف ساخت مدل ارائه مي گردند و در آخر.
٣-٢- متغيرها، پارامترها و مجموعه ها
انديس ها، متغيرها و پارامترها را به صورت زير معرفي ميکنيم :
i: انديس مربوط به دروس
j : انديس کد درس
l : انديس استاد
d : انديس روز
t : انديس ساعت (بازه زماني)
S : انديس گروه دانشجويان
اگر کلاس i ام کد j ام توسط استاد l ام در ساعت t از روز d ارائه گردد مقدار يک ميگيرد و در غير اين صورت صفر است .
اگر کلاس i ام کد j ام توسط استاد l ام در ساعت t از روز d ارائه گردد و گروه S ام دانشجويان در آن ثبت نام کنند مقدار يک ميگيرد و در غير اين صورت صفر است .
اگر کد j ام کلاس سه واحدي i ام دوجلسه در هفته فرد و يک جلسه در هفته زوج داشته باشد مقدار يک و اگر يک جلسه در هفته فرد و دو جلسه در هفته زوج داشته باشد مقدار صفر ميگيرد.
انحراف هاي مثبت و منفي تعداد کلاس هاي گروه دانشجويان S ام در بسته زماني k ام در روز d ام از تعداد کلاس هاي مطلوب .
:اگر گروه دانشجويان S ام در بسته زماني k ام در روز d ام کلاس داشته باشند يک و در غيراين صورت صفر است .
: انحراف هاي مثبت و منفي تعداد کلاس هاي استاد l ام در بسته زماني k ام در روز d ام از تعداد کلاس هاي مطلوب .
: اگر استاد l ام در بسته زماني k ام در روز d ام کلاس داشته باشند يک و در غيراين صورت صفر است .
اگر استادl ام کد j درس i را تدريس کند يک و در غير اينصورت صفر است .
: اگر گروه S دانشجويان در کد j درس i ثبت نام کنند يک و در غير اينصورت صفر است .
معرفي مجموعه ها
پارامترها
Ll;Ul: حداقل و حداکثر تعداد ساعاتي که استاد l ام بايد تدريس کند.
ai : ظرفيت کلاس i ام (حداکثر تعداد دانشجوياني که ميتوانند در کلاس درس i ام ثبت نام کنند.)
kS : تعداد دانشجويان گروه S ام دانشجويي
bdt : تعداد اتاق هاي در دسترس براي زمان بندي کلاس در بازه زمانيt ام از روز d ام
mkl : تعداد کلاس هاي مطلوب استاد lام در بسته زماني kام روز d ام
nkS : تعداد کلاس هاي مطلوب گروه دانشجويان S ام در بسته زماني k ام در روز d ام
vi : تعداد واحدهاي درس i
٣-٣- تابع هدف
تابع هدف خطي به صورت زير معرفي ميگردد که شامل شش بخش است :
