پنج شنبه 3 فروردین 1396 | Thursday 23 rd of March 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
1-2 معرفی سیستم های مشابه

مسئله ایجاد جداول زمانبندی ازدسته مسایل NP-Complete بوده، راه حل ها و مطالعات زیادی پیرامون این مسئله ارائه شده است. رویکردهای جدیدی که برای تنظیم مسائل زمانبندی بکار می رود الگوریتم های تکاملی است.الگوریتم های تکاملی خود به چند دسته تقسیم میشوند مانند جستجوی تپه نوردی،روش شبه تاب کاری،ژنتیک و ... الگوریتم ژنتیک یکی از قوی ترین و پرکاربردترین الگوریتم ها در مسائل جستجو و بهینه سازی است و روش کار ان به وسیله اعمال تصادفی اپراتورهای ژنتیکی بر روی کروموزمها ایجاد می شود و اعمال روش تصادفی در مسئله جدول زمانبندی دروس دانشگاهی با توجه به حجم بالای اطلاعات با افزایش زمان در رسیدن به جواب بهینه مواجه می شود.
 مبنای حل مسئله جدول زمانبندی در پروژه حاضر، از روش رنگ امیزی گراف ]4-1[ است. از انجا که محدودیت های همزمانی غیر مجاز تدریس ها در جدول زمانبندی را می توان بر اساس گراف پیاده سازی کرد و با در نظر گرفتن صورت مسئله رنگ امیزی گراف ها، این محدودیت ها را در جدول زمانبندی حل کرد، در این پروژه سعی شده است با معادل سازی قسمت های مختلف جدول زمانبندی با سیستم گراف ها و منطبق کردن ان دو به یکدیگر جدول زمانبندی بهینه ای برای دروس دانشگاهی تهیه کرد و با توجه به تفاوت های رنگ امیزی گراف نسبت به مسئله جدول زمانبندی مانند در نظر گرفتن حداکثر رنگ برای یک سیستم گراف و همچنین حداکثر تعداد گره هایی که باید دارای یک رنگ یکسان باشند.
پرزینا ]5[ (2006) اینگونه عنوان می نماید که:"مسئله جداول زمانی به عنوان یک مسئله NP شناخته شده است، بنابراین هیچ الگوریتمی وجود ندارد که ان را با پیچیدگی زمانی چند جمله ای حل نماید". تمامی محققان در این زمینه اتفاق نظر دارند که: مسائل جداول زمانی دارای فضای پاسخ نمایی بوده و مانند تمامی مسائل NP-Compelete نیاز به استفاده از الگوریتم های هوشمند جهت حل ان اجتناب ناپذیر است.با توجه به توضیحات و پیچیدگی مسئله، روش های مختلفی برای حل این مسئله در مقالات مختلف پیشنهاد شده است که می توان روش جستجوی تابو(ممنوعه) را نام برد.
انواع معمول در طراحی جدول زمانبندی عبارتند از:
الگوریتم های ژنتیکی، الگوریتم های کلنی مورچه ها، الگوریتم های ممتیک
از کارهای انجام شده در این زمینه می توان به موارد متعدد اشاره نمود: اشام، سلیمن و رمدان در دانشکده مهندسی کامپیوتر دانشگاه کایرو ، از دو روش الگوریتم ژنتیک(GA) و رنگ امیزی گراف(GC) برای حل  مسئله طراحی و پیاده سازی نمودند و با استفاده از روش پیشنهادی رنگ امیزی ژنتیک (Genetic Coloring) که با استفاده از دو روش GA و GC برای حل جدول زمانبندی کلاس و امتحان استفاده می کنند]6[. این مقاله فرمول های برنامه نویسی اعداد صحیح از رنگ امیزی رئوس ارائه داده و روش جدیدی با نام “supernodes” را معرفی می نماید، “supernodes” یک زیر گراف کامل است]7[. این مقاله از تکنیک های جستجوی محلی و برنامه نویسی محدودیت استفاده می کند و نشان می دهد که چگونه از یک list-colouring relaxation  در مسئله استفاده می کند]8[.از دیگر روش های استفاده شده می توان به موارد زیر اشاره کرد:  روش الگوریتم جستجوی ممنوعه]9[. روش الگوریتم زنبورعسل]10[. روش الگوریتم ممتیک]11[. روش الگوریتم تکاملی دو مرحله ای]12[.
 در این قسمت ابتدا در مورد چگونگی عملکرد روش رنگ امیزی گراف توضیح مختصری می دهیم.
1-2-1 رنگ امیزی گراف
مساله رنگ امیزی گراف یکی از مسایل کلاسیک مشهوری است، که سالها ذهن دانشمندان علوم کامپیوتر و ریاضی را به خود مشغول کرده است. قدرت و امتیاز اصلی این روش ها به دلیل تولید راه حل های بهینه در زمان بسیار کوتاه می باشد.
هر گراف شامل چندین رأس یا گره است که با یکسری یال به یکدیگر متصل هستند. به دو رأسی که با یک یال به یکدیگر متصل شده اند رأس مجاور یا همسایه گفته می شود. مسئله رنگ امیزی گراف(GCP) به این صورت است که با داشتن گراف G، می خواهیم حداقل تعداد رنگ های لازم برای رنگ امیزی رئوس گراف را بیابیم طوری که هیچ دو رأس مجاوری همرنگ نباشند. حداقل تعداد رنگ های لازم برای این کار، عدد رنگی گراف نامیده می شود.
برای تبدیل مسئله جدول زمانبندی می توان تدریس ها را به عنوان گره در گراف در نظر گرفت و در صورتیکه دو تدریس از نظر همزمانی با یکدیگر غیر مجاز باشند بین ان دو گره یک یال رسم کرد. برای رنگ امیزی گراف تشکیل شده، دوره های زمانی را به عنوان رنگ در نظر می گیریم و به گره ها(تدریس ها) هر کدام یک رنگ(زمان) الصاق می کنیم به طوری که هیچ دو گره مجاوری دارای رنگ(زمان) مشابهی نباشند. برای ارضا کلیه محدودیت های قوی ذکر شده به غیر از محدودیت شماره 3، می توان با اتصال تدریس های مختلف به یکدیگر به صورت زیر:
•     بین تمام دروس در یک ترم یال رسم کرده.
•     بین دروسی که استاد مشترک دارند یال رسم کرده.
•     بین دروس همنیاز نیز یال رسم کرده.
و ایجاد گراف تداخلی دروس سپس رنگ امیزی گراف را انجام داده در پایان برنامه هفتگی دروس ایجاد خواهد شد.
در این پروژه برای رنگ امیزی گراف از الگوریتم RLF  ]13[ استفاده شده است.در ادامه به بررسی این الگوریتم خواهیم پرداخت سپس با یک مثال گراف تداخلی دروس که توسط این الگوریتم ایجاد می شود را نشان خواهیم داد.
 
1-2-2 الگوریتم RLF
الگوریتم RLF توسط Leighton جهت رنگ امیزی گرافهای با ابعاد بزرگ مربوط به مدلهای زمانبندی، ارائه شده است، این الگوریتم مهمترین الگوریتم سازنده در مسأله رنگ امیزی رأسی گراف بشمار می رود و نسبت به سایر الگوریتم های سازنده معرفی شده دارای عملکرد بهتری می باشد.
الگوریتم RLF متشکل از چندین مرحله بوده که در هر مرحله و متوالیا مجموعه های مستقل را می سازد که در هر یک از این مجموعه ها شامل راس های غیر مجاور می باشد.در ادامه نحوه عملکرد این الگوریتم تشریح شده است.
همه راس ها در گراف در یک مجموعه رئوس پردازش نشده UNP ریخته همه رئوس را بر حسب درجه به صورت نزولی مرتب کرده.این عملیات را تا زمانی که هیچ راس پردازش نشده در مجموعه UNP نباشد را اجرا می کنیم:
اولین راس را در مجموعه A قرار داده و ان را با اولین رنگ از مجموعه color رنگ کرده و از مجموعه UNP حذف کرده. لیست nn را مجموعه رئوسی که با A مجاور نیستند را قرار داده.لیست nn دارای رئوسی است که با یکدیگر مجاور بوده پس بزرگترین درجه را در لیست nn را در مجموعه B گذاشته و تمام همسایه های B را از لیست nn حذف کرده.در نتیجه مجموعه ای مستقل که دارای رئوس غیر مجاور می باشند ایجاد خواهد شد.
هدف از الگوریتم RLF در هر مرحله ایجاد مجموعه های مستقل nn با بیشترین اندازه و در عین حال کاهش یال های گراف حاصل از مجموعه رئوس رنگ امیزی نشده پس از اتمام ساخت مجموعه های مستقل nn است.
ساختار کلی الگوریتم RLF به صورت زیر است:
UNP = all of unprocessed nodes.
Order nodes by degree
color =0
1.While (UNP >0)
// there is any unprocessed node
node A= Take the first uncolored node // the most huge degree
Color A with ++color
UNP--
List nn=all of the uncolored nodes that are not the node "A" neighbors
2.while there is any node in nn
B =Take the biggest degree node in nn
// remove B from nn
Color B the same of A
UNP--
Throw away all of B neighbors in nn from nn list.
Loop 2
Loop 1
شبه کد الگوریتم RLF                                                                     
در واقع در هر مرحله به دنبال ان هستیم که مجموعه مستقلی مانند nn ایجاد نماییم به طوری که بیشترین یال های ممکن از گراف کاسته شود، بدین ترتیب یال های باقیمانده در گراف حاصل از رئوس رنگ امیزی نشده باقیمانده در انتهای هر مرحله از الگوریتم مینیمم می شود.
پس از انجام مراحل بالا و رنگ امیزی گراف، مجموعه های مستقل ایجاد می شود که در هر یک از این مجموعه ها شامل تدریس های غیر مجاور می باشد. سپس به هر مجموعه کلاس ها را نسبت داده برای انتساب دروس به کلاس ها از روش کوله پشتی از نوع انتخاب مناسب ترین فضای موجود و نوع کلاس  (BEST FIT DECREASING:BFD) استفاده می کنیم، به طوری که محدودیت قوی شماره 3 " منطبق بودن تدریس با نوع اتاق " را ارضاء نماید. همچنین محدودیت ضعیف شماره 4 " گنجایش کلاس " نیز اعمال می شود.
برای ارضای محدودیت ضعیف شماره 5 "بعضی از دروس شامل دوتدریس هستند" در این برنامه هر درس حداکثر تا چهار بار در هفته می تواند برنامه ریزی شود به این صورت که بر اساس این مقدار به تعداد روزها و زمان هر تدریس اضافه می نماییم.
سپس برای نسبت دادن زمان ها، روز و زمان را به هر مجموعه نسبت می دهیم.
1-2-3 ایجاد گراف تداخلی دروس
نحوه ایجاد گراف را با یک مثال ساده در شکل زیر می بینید.
UNP { 4,5,3,2,1,7,6 }
A:  4       Red
UNP { 5,3,2,1,7,6 }
 nn { 1 }
B:  1       Red
UNP { 5,3,2,7,6 }
مراحل بالا را تکرار می نماییم
A:  5       Blue
UNP { 3,2,7,6 }
 nn { 3,7 }
B:  3       Blue    
         remove  B  from  nn
         remove  7  from  nn
UNP { 2,7,6 }

A: 2        Green
UNP { 7,6 }
 nn { 7,6 }
B:  7        Green
        Remove  B  from  nn
UNP { 6 }
  nn { 6 }
B: 6          Green
         Remove  B  from  nn
UNP {  }
 
شکل1-1 گراف تداخلی دروس

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26