\documentclass[12pt]{report} 
\usepackage[left=1cm,right=1cm,top=1cm,bottom=1cm]{geometry}
\usepackage{roundbox}
\usepackage{xtab}
\usepackage{amsthm,amssymb,amsmath,mathrsfs}
\usepackage{enumerate}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usepackage{forest}
\usepackage{xepersian}

%فراخوانی فونت پی گاراموند برای اعداد
\setdigitfont[Scale=1.3]{PGaramond}
% تعریف قلم‌های فارسی و انگلیسی برای استفاده در بعضی از قسمت‌های متن
\settextfont[Scale=1.3]{B Nazanin}
\theoremstyle{theorem}
\newtheorem{theorem}{قضیه}[section]
\newtheorem{definition}[theorem]{تعریف}
\newtheorem{example}[theorem]{مثال}
\newtheorem{lemma}[theorem]{لم}
\newtheorem{proposition}[theorem]{گزاره}
\newtheorem{corollary}[theorem]{نتیجه}
\newtheorem{remark}[theorem]{ملاحظه}
\newtheorem{treaty}[theorem]{قرارداد}
\newtheorem{rema}[theorem]{تبصره}
\newtheorem{notice}[theorem]{توجه}
\newtheorem{hint}[theorem]{تذکر}
\newtheorem{point}[theorem]{نکته}
\newtheorem{problem}[theorem]{مساله}
\newtheorem{rem}[theorem]{یادآوری}
\newtheorem{hads}[theorem]{حدس}
\newtheorem{notation}[theorem]{نمادگذاری}
\newtheorem{x}[theorem]{}
\newenvironment{solution}{{\bf \noindent \\ حل. } \rm } 

\begin{document}
در این پایان نامه، هدف ما ایجاد یک برنامه زمانبندی کارا و موثر برای یک محیط دبیرستانی واقعی می‌‌باشد که به طور عام تحت عنوان " مسئله جدول 
زمان بندی دبیرستان" شناخته می‌‌شود. این مسئله، که تا کنون مورد علاقه بسیاری از محققان (2014) بوده است
\cite{1} 
شامل لیست بندی هفتگی تمام دروس یک دبیرستان می‌باشد (2012)
\cite{2}
. برای روشن شدن بیشتر موضوع، ما نیاز به تدوین یک سری جلسات تدریس بین دانش آموزان و معلمان هستیم به طوری که جدول زمانی خروجی، کاملا مناسب و مورد پذیرش هر دو طرف تدریس باشد. محدودیت هایی که بایستی مرتفع شوند شامل دو دسته می‌‌باشند. اول محدودیت های سخت و دوم محدودیت های نرم. دسته اول محدودیت ها شامل تمامی‌‌محدودیت هایی هستند که بایستی حتما مرتفع شوند تا جدول زمانی خروجی را بتوان اجرایی نمود. جدول زمانی ای را که تمامی‌‌محدودیت های سخت را مرتفع کرده باشد، با عنوان جدول زمانی قابل اجرا و مطلوب می‌‌شناسیم. دسته دوم محدودیت ها مربوط به خواسته های به خصوص هر دو طرف ذینفع ( معلم و دانش آموز) می‌‌باشد و میزان مرتفع شدن این محدودیت ها میزان کیفیت جدول زمانی خروجی را مشخص می‌‌سازد
\cite{2}. 
مسئله جدول زمان بندی دبیرستان(2012) عموما یکی از سه بخش از مسئله بزرگتری موسوم به مسئله جدول زمانبندی آموزشی می‌‌باشد
\cite{3}
، که دو تای دیگر شامل: مسئله جدول زمان بندی دروس دانشگاه (2013)
\cite{4}
 و مسئله جدول زمان بندی 
امتحانات 
(2012)
است\cite{5}. اولین موضوعی که در مورد جدول زمانی برای دروس بایستی مدنظر قرار گیرد، قراردادن هر درس در یک زمان( یا مجموعه ای از زمان ها) است به طوری که زمان این درس با زمان درسهای دیگر که توسط یک دانش آموز مشخص انتخاب شده است تداخلی نداشته باشد.جدول زمانی امتحانات نیز شامل، از یک سو برنامه ریزی امتحانات یکسری از درس های دبیرستان با پیشگیری از همزمانی وقوع دو امتحان برای یک دانش آموز و از سوی دیگر اتخاذ زمان کافی واقع بین دو امتحان تا حد ممکن می‌‌باشد. تمامی‌‌این سه بخش از مسئله ، به نوبه خود و عموما از نوع 
$NP- Complete$
 می‌‌باشد که به طور کامل در منابع شرح داده شده اند
\cite{6,7,8}
 . این بدان معناست که حتی با استفاده از یک ابر رایانه و استفاده از یک روش غیرابتکاری و با توجه به ورودی های بسیار زیاد، پیدا کردن یک پاسخ تکی و ساده کاری بسیار دشوار است. 
تفاوت های بسیاری که در مسئله جدول زمانی دبیرستان ها و تلاش ها برای حل این مسئله دیده می‌‌شود را می‌‌توان در منابع 
\cite{1,9,10,11}
 مشاهده نمود. تفاوت های بنیادی که در مسئله جدول زمانی دبیرستان و روش‌های حل آن دیده می‌‌شود عمدتا به منحصر به فرد بودن سیستم آموزشی هر کشور باز می‌‌گردد. برای مثال، بولاند و همکاران (2008) تلاش کردند تا از روش بلاک کردن سال تحصیلی و مسئله جمعیتی در مورد کشور استرالیا دو مدل برنامه ریزی خطی صحیح را تولید نموده و مسئله را به این صورت حل نمایند
 \cite{12}
 . مورا و اسکارافیچی (2013) مسئله جدول زمان بندی دبیرستان را برای سه دبیرستان در برزیل و با استفاده از یک پروسه ابتکاری جستجوی تطبیقی تصادفی حریصانه اساسی  که بهینه سازی آن نیز به روش بهبود مسیر صورت می‌‌گیرد حل نموده اند
 \cite{13}
 . سانتوس و همکاران (2012) نیز از یک روش ستون سازی برای ساخت کران برای مجموعه ای از داده‌ها استفاده کردند 
%  برای مثال، بولاند و همکاران تلاش کردند تا از روش بلاک کردن سال تحصیلی و مسئله جمعیتی در مورد کشور استرالیا دو مدل برنامه ریزی خطی صحیح را تولید نموده و مسئله را به این صورت حل نمایند
% \cite{12}
% . مورا و اسکارافیچی مسئله جدول زمان بندی دبیرستان را برای سه دبیرستان در برزیل و با استفاده از یک پروسه ابتکاری جستجوی تطبیقی تصادفی حریصانه اساسی  که بهینه سازی آن نیز به روش بهبود مسیر صورت می‌‌گیرد حل نموده اند
% \cite{13}
% . سانتوس و همکاران نیز از یک روش ستون سازی برای ساخت کران برای یک سری مجموعه داده و آن‌ها نیز در کشور برزیل بهره برده اند
 \cite{14}
 . سورنسن و استیدسن (2012) نیز یک الگوریتم جستجوی همسایگی تطبیقی بزرگ برای حل مسئله جدول زمانبندی مدارس در کشور دانمارک ارائه کرده اند
 \cite{15}
 . آولا و همکاران (2007) نیز از یک الگوریتم ترکیبی شامل یک شبیه سازی برای حل اولیه و یک جستجوی همسایگی گسترده برای بهبود آن استفاده کردند که در مورد دو نمونه واقعی در کشور ایتالیا مورد استفاده قرار گرفت
 \cite{16}
 . سرانجام، پست و همکاران (2012)، یک الگوریتم انتقال دوره ای برای مسئله جدول زمان‌بندی مدارس استفاده کرده و آن را در چهار دبیرستان آلمانی و یک دبیرستان بریتانیایی مورد آزمایش قرار دادند\cite{17}.
اخیرا، مقالات زیادی در مورد تکنیک های ویژه حل مسئله جدول زمانی دبیرستان ها منتشر شده است
\cite{18,19,21, 23,24,25,26,27,28}
. راگاوجی و پیلای (2012) اجرای الگوریتم ژنتیک را در مقابل برنامه ریزی ژنتیک در حل یک سری از مسائل جدول زمان بندی دبیرستان مورد مقایسه قرار داده اند\cite{18}. سورنسن و همکاران (2012) یک الگوریتم را بر اساس جستجوی همسایگی تطبیقی گسترده برای حل مسئله جدول زمان بندی دبیرستان توصیف نموده اند\cite{19} که در مسابقات بین المللی جدول های زمان بندی  در سال 2011 مورد استفاده قرار گرفت\cite{20}. دومروس و هومبرگر (2012) یک الگوریتم تکاملی برای مسئله جدول زمان بندی دبیرستان ارائه داده اند\cite{21} که جدول های زمانی به صورت غیرمستقیم نشانه گذاری کرده در حالی که جستجوی تکاملی به کمک اصل جمعیتی  
(1+1) 
(2002) کنترل می‌‌گردد\cite{22}. کالندر و همکاران (2013) نیز یک مسئله جدول زمان بندی درسی را به صورت شرایط محور و در دانشگاه یدیپ توصیف کرده و به عنوان روش حل نیز یک روش انتخابی فراابتکاری تکراری معرفی نموده اند\cite{23}. تیم استراتژی های جستجوی فراابتکاری و جداول زمان بندی (2014) یک روش جستجوی تصادفی استاندارد معرفی نموده اند که به طور معناداری یک انتخاب فراابتکاری را با یک مکانیزم پذیرش تطبیقی به کار می‌‌برد\cite{24}. دا فونسکا و همکاران (2014)، یک روش جستجوی محلی را برای مسئله جدول زمان بندی دبیرستان ها ارائه کرده اند\cite{25}. احمد و همکاران(2015)، کاربرد یک طیف انتخاب فراابتکاری در ترکیب با اجزای با قابلیت استفاده مجدد برای جدول زمان بندی دبیرستان ها به تکامل رسانده اند\cite{26}. آل یعقوب و شیرالی (2015) بر روی دو روش تجزیه کار کردند تا یک مسئله جدول زمان بندی دبیرستان را در یک مطالعه موردی مربوط به سیستم آموزشی کشور کویت حل نمایند\cite{27}. سر انجام، درنلس و همکاران از سه نوع متفاوت از تجزیه- کلاس، معلم و روز- در جهت حل مسئله جدول زمان بندی دبیرستان استفاده کرده اند. 
\begin{table}[!h]
\centering
\begin{tabular}{|p{3.3in}|p{0.9in}|p{1.6in}|} \hline 
تحقیقات انجام شده & زمان انجام تحقیق & رویکرد حل(روش بکار رفته) \\ \hline 
بورک و همکاران & ( 2007) & رنگ آمیزی گراف \\ \hline 
اسماعیلیان و عبدالهی\newline جورکی، منتظری و موسوی \newline علیرضایی، منصورزاده و خلیلی & ( 1395)\newline  ( 1390) \newline ( 1385) & برنامه ریزی ریاضی \\ \hline 
ویریس \newline ژانگ لائو & ( 2005)\newline  ( 2005) & برنامه ریزی محدودیت ها \\ \hline 
منجمی، مسعودیان، استکی و نعمت بخش کپتا و میشرا  &  ( 1388)\newline  (2014) & الگوریتم ژنتیک (GA) \\ \hline 
کاستاچ \newline آیکانی & ( 2005)\newline  ( 2009) & الگوریتم SA \\ \hline 
الوازرو والدز، گرسکو و تاماریت. آلاداگ، هوکالگو و باسلاران & ( 2002) \newline ( 2009) & الگوریتم TS \\ \hline 
نارگر، مایر، چاوتال و رایدل & ( 2012) & الگوریتم ACO \\ \hline 
بلیگیانیس & ( 2017) & الگوریتم CSO \\ \hline 
جورج و همکاران جیم، کیم \newline لوگاناتانو الزاقبه \newline  عبداله تارابیه، عبدالله، مک کالم \newline مک مولان & ( 2013)\newline (2001) \newline ( 2015).\newline  ( 2010) & سایر الگوریتم های فراابتکاری \\ \hline 
چادوری ودی. گلاب پور، شیرازی، فراهی، کوتیانی فربیگی & ( 2010)\newline  ( 2008) & روش های فازی \\ \hline 
امین طوسی و حدادنیا. شاتناوی، الربابه و بنی اسماعیل & ( 2005)\newline  ( 2010) & الگوریتم های خوشه بندی \\ \hline 
وانگماتیکولیانگ و پارنجیپ. \newline یانگ و همکاران & ( 2011)\newline  ( 2006) & سیستم های عامل محور \\ \hline 
سانتیاگو موزارس و بندیسنتی & ( 2005) & الگوریتم های ابتکاری \\ \hline 
\end{tabular}
\end{table}


\begin{table}[!h]
\centering
\begin{tabular}{|p{0.5in}|p{0.5in}|p{0.6in}|p{0.5in}|p{3in}|} \hline 
نام نویسنده یا نویسندگان& مرجع & سال انتشار & رویکرد& شرح \\ \hline
سوخا
\footnotemark[1]
 & \cite{11}
& 2003 & الگوریتم هوشمند ازدحام & در این مقاله دو الگوریتم کلونی مورچه
\footnotemark[2]
 و الگوریتم مورچگان ماکس-مین
 \footnotemark[3]
  برای حل مسأله‌ی جدول زمانی دروس دانشگاه استفاده شده است در هر مرحله از هر دو الگوریتم، هر مورچه یک تخصیص کامل از رویدادها به مقاطع زمانی را با کمک فرآیندهای ابتکاری و اطلاعات ف؟؟ها انجام می‌دهد. \\
\hline
سویانتو
\footnotemark[4]
 & \cite{19}& 2010& الگوریتم تکاملی& سویانتو الگوریتم ژنتیکی را برای جدول زمانی  دروس دانشگاه و تقسیم‌بندی دانشجویان ارائه نمود. الگوریتم وی بر اساس یک قاعده ابتکاری آزمندانه تعدادی جواب شدنی که همه‌ی محدودیت‌های سخت را برآورده نماید، ایجاد می‌کند. سپس یک برنامه‌ی جهش هدایت شده برای کاهش نقض محدودیت‌های نرم با حفظ شدنی بودن جواب مورد استفاده قرار داده شده است. \\ \hline
کوستاچ
\footnotemark[5]
 & \cite{22} & 2004 & الگوریتم جستجوی محلی & این الگوریتم در2003-$ITC$ با کمک یک الگوریتم ابتکاری مبتنی بر تبرید شبیه سازی
 \footnotemark[6]
  برنده شد. در این پژوهش ابتدا یک جدول زمانی شدنی ایجاد می‌‌شود و سپس این جدول با کمک تبرید شبیه سازی شده بهبود می‌یابد. \\ \hline
بورک
\footnotemark[7]
 و همکاران & \cite{28}& 2007 & الگوریتم رنگ آمیزی گراف& یک روش فرا ابتکاری مبتنی بر گراف برای جدول زمانبندی امتحانات توسعه یافت. یک رویکرد جست و جوی ممنوعه برای جستجوی جایگشت‌های ساختار ابتکاری گراف که برای ایجاد جداول استفاده می‌شود، به کار رفت. \\ \hline
لاخ و لوبکه
\footnotemark[8]
 & \cite{36}& 2012 & روش‌های دقیق & در این پژوهش  داده‌های پایه‌ی جدول زمانبندی دروس دانشگاهی مبتنی بر گروه درسی دانشگاه اووین توسط یک رویکرد تجزیه‌ی دو مرحله‌ای حل شد.
خلاصه‌ی دو مرحله‌ی تجزیه ابتدا تخصیص جلسات دروس بر مقاطع زمانی در مرحله‌ی اول و سپس اتاق‌ها به جلسات در مرحله‌ی دوم است.
\\
\hline
\end{tabular}
\end{table}
\begin{tablenotes}\footnotesize
\begin{LTRitems}
\item[1] \lr{Socha}
\item[2] \lr{Ant Colony System}
\item[3] \lr{Max-Min Ant System}
\item[4] \lr{Suyanto}
\item[5] \lr{Kostuch}
\item[6] \lr{Simulated Annealing}
\item[7] \lr{Burke}
\item[8] \lr{Lach and Lobbecke}
\end{LTRitems}
\end{tablenotes}
در جدول  تعدادی از تحقیقات در مورد مسئله جدول زمانبندی دبیرستان که در سال های مختلف و با رویکردهای مختلف حل شده به همراه نام محقق آورده شده است.
 
الگوریتم های مبتنی بر بهینه سازی ازدحام گربه، متعلق به خانواده بزرگی از الگوریتم ها می‌‌باشد که به نوعی خروجی مکانیزم های طبیعت است که رفتار گروهی سیستم های فیزیکی خود سازمان ده غیر توزیعی را تقلید می‌‌کند
\cite{29,30,31,32}
 الگوریتم های ازدحام گربه ابتدا توسط چو و همکاران معرفی شدند
\cite{30}. انگیزه کلیدی برای پیشنهاد این طبقه جدید الگوریتم های مبتنی بر جمعیت مشاهدات آن‌ها از رفتار گربه و به خصوص راه هایی که گربه ها برای جستجو و شکار در محیط زیست خود به کار می‌‌بردند بود. اگرچه که تمامی ‌‌گربه ها با غریزه شکار متولد می‌‌شوند و زمانی که هنوز بچه هستند، تحت آموزش مادر خود به سر می‌‌برند تا شکار را بیاموزند. علاوه بر این، گربه ها به صورت وراثتی دارای یک ذات کنجکاو متغیر بر هر چیزی که در اطراف آن‌ها حرکت می‌‌کند می‌‌باشند. هر چند که آن‌ها بیشتر زمان خود را در حال دراز کشیده روی زمین به سر می‌‌برند و حتی اگر خواب نباشند، دراز کشیدن و چرت زدن را دوست دارند. در حالی که اگر شما آن‌ها را ببینید به نظر می‌‌رسد که حیوانات تنبلی هستند، اما در حقیقت، آن‌ها همیشه کاملا در حال مراقبت و مشاهده اطراف و آمادگی برای انجام یک عمل سریع هستند. در نتیجه، حتی وقتی که آن‌ها را در حال استراحت می‌‌بینیم، آن‌ها دائما محیط اطراف خود را با چشم هایشان زیر نظر دارند تا هر زمان که لازم شد به سرعت وارد عمل شوند.
زمانی که الگوریتم های ازدحام گربه اخیرا و برای بارهای اول مورد آزمایش قرار گرفت، نتایج حاصل از آن‌ها، مخصوصا در بسیاری از مسائل بهینه سازی که دارای محدودیت های زیاد و سختی بودند بسیار راضی کننده بود
\cite{33,34,35,36,37,38}
.  پاندا و همکاران، کار شناسایی سیستم پاسخ دهی تکانه نامتناهی را به عنوان یک مسئله بهینه سازی فرمول بندی کرده و از بهینه سازی ازدحام گربه به منظور توسعه یک قانون آموزشی جدید مبتنی بر جمعیت برای آن مدل بهره بردند\cite{33}. وانگ و همکاران یک استراتژی مبتنی بر ازدحام گربه را برای به دست آوردن حل بهینه یا نزدیک به بهینه مسئله کیفیت تصویری تغییر دادند\cite{34}. پرادهان و پاندا بهینه سازی ازدحام گربه را در جهت طراحی یک الگوریتم تکاملی چند منظوره جدید گسترش دادند
\cite{35}.  تسای و همکاران یک روش ازدحام گربه موازی برای حل مسائل بهینه سازی عددی ارائه دادند\cite{36}. کومار و همکاران، یک جاگذاری و اندازه گزینی ژنراتورهای توزیعی چندگانه برای دستیابی به قابلیت اطمینان بیشتر سیستم اورآل در شبکه های توزیع اولیه در مقیاس  بزرگ و با استفاده از بهینه سازی ازدحام گربه پیشنهاد کردند\cite{37}.
سرانجام، هدیل و صباح یک الگوریتم ازدحام گربه بهبود یافته برای حل مسائل بهینه سازی عددی ارائه کردند\cite{38}.
\\در این پایان نامه، ما بررسی خواهیم کرد که آیا یک الگوریتم مبتنی بر بهینه سازی ازدحام گربه، می‌‌تواند به طور موثری مسائل جدول زمان بندی مدارس را حل نماید یا نه. در این پایان نامه ما با دو بعد سر و کار داریم:
\begin{itemize}
\item	ما اصل عملکرد یک الگوریتم مبتنی بر بهینه سازی ازدحام گربه را  در جهت حل مسئله جدول زمان بندی دبیرستان ها به کار می‌‌بریم که علاوه بر سهولت استفاده کاملا از لحاظ زمانی با سرعت عمل می‌کند.
\item	الگوریتم مبتنی بر بهینه سازی ازدحام گربه ترکیبی کار مدیریت دستیابی به نتایج زمانی غیر پیچیده و کاملا راضی کننده در مقایسه با بهترین روش های موجود انجام می‌‌دهد. علاوه براین، منجر به یک روش قطعی برای مسئله جدول زمان بندی دبیرستان ها خواهد شد
\cite{1,10,39,40,41,42,43,44,45}
.
علاوه بر تمام این ها، این الگوریتم، برای داده های کاملا واقعی که از دبیرستان های مختلف جمع آوری می‌‌شوند به کار می‌‌روند. 
\end{itemize}
\end{document}