\documentclass[oneside,a4paper,notitlepage,10pt]{book}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{fancyhdr}
\usepackage{enumerate}
\usepackage[onehalfspacing]{setspace}
\usepackage{pifont}
\renewcommand{\labelenumi}{\roman{enumi}}
\usepackage{xepersian}
\renewcommand{\baselinestretch}{1.5}\normalsize
\renewcommand{\contentsname}{}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[OL,EL]{\thepage}
\fancyhead[OR]{پیوست ب. روش‌های بهینه‌سازی دقیق}
\fancyhead[ER]{پیوست ب. روش‌های بهینه‌سازی دقیق}
\renewcommand\headrule{}
\begin{document}
\appendix
\setcounter{chapter}{1}
%\appendix
\chapter[روش‌های بهینه‌سازی دقیق]{روش‌های بهینه‌سازی دقیق}\label{}
\tableofcontents
\section{معرفی}
مسائل برنامه‌ریزی و زمان‌بندی به‌طور ذاتی ساده‌اند و همانند برنامه‌ریزی خطی که به‌آسانی قابل حل در الگوریتم‌های کارای موجود هستند قابل فرمول‌بندی می‌باشند. این الگوریتم‌های کارا معمولا به‌عنوان الگوریتم‌های زمان چندجمله‌ای معرفی می‌شوند. این مسئله می‌تواند توسط یک الگوریتم کارا و زمان چندجمله‌ای حل شود، که مثال‌های خیلی بزرگ‌ از‌ آن مسئله با صدها یا هزاران فعالیت می‌توانند در یک مدت زمان نسبتا کوتاه با کامپیوتر حل شود.\\
از این رو، بسیاری از مسائل برنامه‌ریزی وجود دارند که ذاتا بسیار سخت می‌باشند. این مسائل به عنوان مسائل $NP-hard$ معرفی می‌شوند. این مسائل معمولا مسائل ترکیبی هستند که نمی‌توانند با مسائل خطی حل شوند و هیچ قانون یا الگوریتم ساده‌ای که جواب‌های بهینه در مدت زمان محدود کامپیوتر به‌دست آورد، وجود ندارد. اغلب ممکن است که برنامه عددصحیح یا برنامه ریزی گسسته مناسبی برای چنین مسائلی وجود داشته باشد، اما حل اینگونه مسائل ممکن است به یک زمان بسیار زیاد کامپیوتری نیاز داشته باشد.\\
دسته‌های متنوع و مفیدی از روش‌ها برای به‌دست آورردن جواب‌های بهینه برای مسائل $NP-hard$ وجود دارد. یکی از این دسته‌ها، روش‌های برنامه‌ریزی پویا را است. برنامه‌ریزی پویا یکی از گسترده‌ترین تکنیک‌های مورد استفاده برای پرداختن به مسائل بهینه‌سازی ترکیبی است. برنامه‌ریزی پویا روشی است که برپایه‌ی رویکرد تقسیم و موفقیت می‌باشد. این روش همانند مسائل $NP-hard$ می‌توانند برای مسائلی که در زمان چندجمله‌ای قابل حل هستند، به‌کار برده شوند.\\
اگر یک مسئله‌ برنامه‌ریزی بتواند توسط یک برنامه‌ریزی عددصحیح فرموله شود، آنگاه از تکنیک‌های مختلف دیگری نیز قابل حل است. شناخته شده‌ترین روش‌ها برای حل برنامه‌ریزی عدد صحیح، عبارت‌اند از:
\vspace*{-2mm}
\begin{enumerate}[\hspace*{1em}($i$)]
\item 
  روش‌های شاخه و کران
\vspace*{-3.8mm}
\item
 روش‌های چندسطحی برش
 \vspace*{-3.8mm}
\item
روش‌های ترکیبی 
\end{enumerate}
اولین دسته از روش‌ها، روش شاخه و کران است که یکی از محبوب‌ترین دسته‌ها از تکنیک‌های مورد استفاده در برنامه‌ریزی عدد صحیح است. شاخه‌کردن یک تقسیم‌بندی از فضای جواب ارائه می‌دهد و هر بخش از فضای جواب به‌طور مجزا درنظر گرفته می‌شود. محدود کردن (کرانی کردن)، به ایجاد کران برای بخش‌هایی از فضای جواب اشاره می‌کند( با فرض مینیمم کردن هدف). اگر کران پایینی یافت شود که در یک بخش از فضای جواب بزرگ‌تر از جواب صحیحی باشدکه قبلا در بخش دیگری از فضای جواب به‌دست آمده است، آنگاه بخش مربوط به کران بزرگتر می‌تواند نادیده گرفته شود. دومین دسته از روش‌ها، روش‌های برنامه‌ریزی برش است  و بر آزادسازی برنامه‌ریزی خطی در برنامه‌ریزی عدد صحیح تمرکز دارد. این روش‌ها محدودیت‌های خطی اضافی را تولید می‌کنند، یعنی برنامه‌ریزی برش برای متغیرهایی که باید صحیح شوند اعمال می‌شود. تعداد نامعادلات محدودیت‌های اضافی مجموعه‌ی شدنی بیشتر از نامعادلات مجموعه‌های اصلی خطی بدون برش در جواب‌های صحیح است. حل کردن آزادسازی $LP$ از $IP$ با محدودیت‌های اضافی یک جواب جدید را به‌دست می‌آورد که ممکن است صحیح باشد. اگر جواب صحیح باشد، روش متوقف می‌شود و جواب به‌دست آمده به‌عنوان جواب نهایی برای مسئله اصلی $IP$ درنظر گرفته می‌شود. اگر متغییرها عدد صحیح نباشند تعداد معادله بیشتری ایجاد می‌شود.\\
روش‌های ترکیبی معمولا ترکیب ایده‌هایی از روش‌های متنوع و مختلف است. به‌عنوان مثال روش برنامه‌ریزی صفحه برش در سال‌های اخیر در میان استفاده کنندگان از این روش محبوب بوده‌اند. وقتی روش شاخه و کران در تکنیک‌های برنامه‌ریزی برش استفاده ‌شود، آن‌را به‌عنوان شاخه و برش معرفی می‌کنند.
\section{برنامه‌ریزی پویا}
برنامه‌ریزی پویا اساساً یک برنامه شمارشی کامل است که از طریق یک روش تقسیم و موفقیت، برای به حداقل رساندن مقدار مورد محاسبه، تلاش می‌کند. این روش به‌صورت حداقل‌‌کردن یک سری از زیرمسئله‌ها تا یافتن یک جواب برای مسئله اصلی است. جواب بهینه را برای هر زیرمسئله و سهم آن در تابع هدف را تعیین می‌کند. در هر تکرار، با استفاده از اطلاعاتی که در جواب‌های زیر مسئله‌های پیشین به‌دست‌ آورده است، یک جواب بهینه را برای زیرمسئله فعلی پیدا می‌کند.\\ برنامه‌ریزی پویا با سه نوع رابطه مشخص می‌شود، که عبارت‌اند از:
\vspace*{-2mm}
\begin{enumerate}[\hspace*{1em}($i$)]
\item شرایط اولیه
\vspace*{-3.8mm}
\item رابطه بازگشتی و
\vspace*{-3.8mm}
\item مقدار تابع بهینه 
\end{enumerate}
در برنامه‌ریزی پویا برای رسیدن به جواب، می‌توان از یکی از روش‌های حل برنامه‌ریزی پویای پیشرو و برنامه‌ریزی پویای پسرو استفاده نمود. مثال زیر یک برنامه‌ریزی پویای پیشرو را نشان می‌دهد.\\
\\
\textbf{مثال ب.1.2(فرمول برنامه‌ریزی پویای پیشرو)}.
یک ماشین و $n$ فعالیت را درنظر بگیرید. اگر فعالیت $j$ در زمان $c_j$ کامل شود و یک هزینه $hj(cj)$ در بر داشته باشد. مسئله مورد بررسی این است که، کارها به‌گونه‌ای ترتیب داده شوند که هدف
\begin{equation*}
\sum_{j=1}^n h_j(C_j)
\end{equation*}
حداقل شود. این مسئله، یک مسئله بسیار مهم در تئوری برنامه‌ریزی است که شامل بسیاری از توابع هدف مهم و خاص است، می‌باشد. به عنوان مثال،  هدف یک تعمیمی از هدف  است، که از این رو یک مسئله $NP-hard$ می‌باشد. فرض کنید $j$ یک زیر مجموعه از $n$ فعالیت باشد و فرض کنید که همه‌ی فعالیت‌هایی که در $j$ هستند قبل از فعالیت‌هایی که در مجموعه $j$ نیستند انجام شوند. فرض کنید 
\begin{equation*}
V(J)=\sum_{j\in J} h_j(C_j)
\end{equation*}
مجموعه‌ای از فعالیت‌های $j$ باشند که در ابتدا انجام می‌شوند. فرمول برنامه‌ریزی پویا در مسئله به شرایط اولیه، مقدار تابع هدف و رابطه بازگشتی بستگی دارد.\\
\textit{شرایط اولیه:}
\begin{equation*}
V({j})=h_j(p_j) \hspace*{1.5cm}  j=1,2,...,n
\end{equation*}
\textit{رابطه بازگشتی:}
\begin{equation*}
V(J)=\min_{j\in J}\Big (V(J-\{j\})+h_j(\sum_{k\in J}p_k)\Big)
\end{equation*}
\textit{مقدار تابع بهینه:}
\begin{equation*}
V(\{1,...,n\})
\end{equation*}
ورای این روش برنامه‌ریزی پویا نسبتاً آسان است. در هر عمل از توالی بهینه برای یک زیرمجموعه از فعالیت‌ها، (یک زیر مجموعه $j$ که شامل $L$ فعالیت است) تعیین می‌شود و فرض می‌شود این زیرمجموعه در ابتدا اعمال می‌شود. این روند برای هر زیرمجموعه با اندازه $L$ انجام می‌شود. که تعداد زیرمجموعه‌ها
$n!/l!(n-l)!$
زیرمجموعه می‌باشد. برای هر زیرمجموعه، سهم $L$ فعالیت زمان‌بندی شده برای تابع هدف محاسبه می‌شود. از طریق رابطه‌ بازگشتی به همه‌ی زیرمجموعه‌هایی که شامل $L+1$ فعالیت است، گسترش داده می‌شود. هریک از $L+1$ فعالیت به عنوان یک کاندیدا که در ابتدا باید انجام شود، در نظر گرفته می‌شود. وقتی که با استفاده از رابطه بازگشتی توالی واقعی L فعالیت از زیرمجموعه‌های کوچکتر مورد توجه قرار نمی‌گیرد، تنها بخشی از فعالیت‌های $L$ در هدف شناخته می‌شود. پس از اینکه ارزش $V({1,2,…n})$ مشخص شد، توالی بهینه از طریق یک روش پسرو و ساده به‌دست می‌آید.\\
محاسبه‌ی پیچیدگی این مسئله می‌تواند همانند آنچه که در زیر آمده است باشد. ارزش $V(J)$ باید برای همه‌ی زیرمجموعه‌هایی که شامل $L$ فعالیت می‌باشد مشخص شود. که $n!/l!(n-l)!$
زیرمجموعه است. همچنین تعداد اعداد تخمینی که بایستی انجام شود، به تعداد زیر می‌باشد: 
\begin{equation*}
\sum_{l=1}^n \dfrac{n!}{l!(n-l)!}=O(n^2).
\end{equation*}
\textbf{مثال ب.2.2(کاربرد برنامه‌ریزی پویای پیشرو)}.
مسئله‌ی مثال قبل را با فعالیت‌های زیر درنظر بگیرید.
\begin{center}
\addtolength{\tabcolsep}{7pt}
\begin{tabular}{1111}
\hline فعالیت‌ها & 1 & 2 & 3\\ \hline $p_j$ & 4 & 3 & 6\\  $h_j(C_j)$ & $C_1 +C_^2$ & $3+C_2^3$ & $8C_3$ \\ \hline 
\end{tabular}
\end{center}
همچنین
$V(\{1\})=20$
و
$V(\{2\})=30$
و
$V(\{3\})=48$
هستند. دومین اثر متقابل روش همه مجموعه‌های شامل 2 فعالیت را درنظر بگیرید. به‌کار بردن رابطه بازگشتی حاصل می‌دهد:
\[
\begin{split}
V(\{1,2\})&=\min \Big(V(\{1\})+h_2(p_1+p_2), V(\{2\})+h_1(p_1+p_2)\Big) \\
&=\min(20+346, 30+56)=86 
\end{split}
\]
همچنین اگر فعالیت‌های 1 و 2 بر فعالیت‌های 3 مقدم باشند، آنگاه فعالیت 2 باید ابتدا انجام شود و فعالیت 1 به‌عنوان دومین فعالیت انجام شود. در روش مشابه می‌توان مشخص کرد که  $V{(1,3)}=100$ با فعالیت 1 ابتدا انجام و فعالیت 3 به‌عنوان دومین فعالیت انجام می‌گردد و $V{(2,3)}=102$ با فعالیت 2 ابتدا انجام و فعالیت 3 به‌عنوان دومین فعالیت انجام می‌شود. آخرین عمل این روش مجموعه {1و2و3} را درنظر بگیرید.
\\[-5mm]
\[
\begin{split}
V(\{1,2,3\})=\min \Big(&V(\{1,2\})+h_3(p_1+p_2+p_3),\\
&V(\{2,3\})+h_1(p_1+p_2+p_3), \\
&V(\{1,3\})+h_2(p_1+p_2+p_3) \Big) . \\
V(\{1,2,3\})= \min \Big(&86+104, 102+182, 100+2200 \Big) =190
\end{split}
\]
به این ترتیب، فعالیت 1 و فعالیت 2 باید ایتدا و فعالیت 3 بعد از آنها انجام شود. ترتیب بهینه 2 و 1 و 3 است و مقدار تابع هدف 190 می‌باشد.\\
در مثال زیر مسئله‌ی مشابه قبل با برنامه‌ریزی پویای پسرو آمده است. در برنامه‌ریزی مسائل پسرو، می‌توان برای مسائلی که دارای یک بازه که به‌طور مستقل برنامه‌ریزی می‌شوند، استفاده نمود (یعنی برای مسائل تک‌ماشینی که بدون توالی مستقل انجام می‌شوند و برای مسائل چندماشینی با فعالیت‌هایی که زمان‌های پردازش یکسان دارند). \\
استفاده از برنامه‌ریزی پویای پسرو از اهمیت بالایی برخوردار است که مشابه روش برنامه‌ریزی پویایی است که در قسمت بعدی برای مسائل برنامه‌ریزی آماری بحث می‌شود.\\[0.5cm]
\textbf{مثال ب.3.2 (فرمول برنامه‌ریزی پویای پسرو)}.\\
دوباره یک مسئله برنامه‌ریزی تک‌ماشینی با تابع هدف  بدون حق‌تقدم را درنظر بگیرید. واضح است که بازه‌ی $C_{max}$ به طور مستقل برنامه‌ریزی می‌شود و آخرین فعالیت در $C_{max}$ کامل می‌شود که برابر با مجموع زمان‌های $n$ پروسه است. \\
همانند قبل $j$ یک زیرمجموعه از $n$ فعالیت را نشان می‌دهد و فرض می‌شود که  $j$ در ابتدای فرایند باشد. $J^c$ را متمم $j$ بنامید. همچنین مجموعه $j^c$ نیز آخرین فرایند باشد. $V(J)$ را حداقل سهم مجموعه $j^c$ برای تابع هدف نشان دهید. به‌عبارت دیگر، $V(j)$ حداقل هزینه‌ی اضافی برای تکمیل همه‌ی فعالیت‌های باقی‌مانده بعد از فعالیت‌های مجموعه $j$ که کامل شده اند، می‌باشد.\\ 
در روش برنامه‌ریزی پویای پسرو، شرایط اولیه، رابطه بازگشتی و مقدار تابع بهینه به صورت زیر است. \\
شرایط اولیه:
\begin{equation*}
V(\{1,...,j-1,j+1,...n\})=h_j(C_{max}) \hspace*{1.5cm}  j=1,2,...,n
\end{equation*}
رابطه بازگشتی:
\begin{equation*}
V(J)=\min_{j\in J^c} \Big( V(J\cup\{j\}+h_j(\sum_{k\in J \cup\{j\}}P_k)\Big)
\end{equation*}
مقدار تابع هدف بهینه:
\begin{equation*}
V(\oslash)
\end{equation*}
همانند قبل این روش نسبتاً آسان است. در هر تکرار، توالی بهینه برای یک زیر مجموعه از $n$ فعالیت، یک زیرمجموعه $j^c$ با اندازه $L$ مشخص می‌شود، با این فرض که این زیرمجموعه به‌عنوان آخرین زیرمجموعه انجام می‌شود. از طریق رابطه‌ی بازگشتی این کار برای همه‌ زیرمجموعه‌های با اندازه $L+1$ انجام می‌شود. توالی بهینه وقتی که زیرمجموعه شامل همه‌ی فعالیت‌ها باشد، به‌دست می‌آید. در مثال ب 2.1 مجموعه‌ی $j$، مجموعه‌ای از فعالیت‌هایی است که قبلاً برنامه‌ریزی شده‌اند، در حالی که، در این مثال مجموعه $j$ مجموعه‌ای از فعالیت‌هایی است که درحال انجام شدن‌ هستند.
\section{روش‌های بهینه‌سازی برای برنامه‌ریزی عدد صحیح}
برنامه‌ریزی‌های عدد صحیح اغلب با روش‌های شاخه و کران حل می‌شوند. یک روش شاخه و کران پایه‌ای می‌تواند به‌صورت زیر تعریف شود. فرض کنید با آزادسازی مسئله $LP$ به $IP$ (که $IP$ بدون محدودیت‌های صحیح است) یک حل به‌دست آید. اگر حل به‌دست‌آمده از $LP$ عدد صحیح $X$ باشد آنگاه این جواب به‌دست‌آمده برای مسئله‌ی عدد صحیح اصلی نیز بهینه است. اگر $X$ صحیح نباشد، آنگاه مقدار بهینه $LP‌$ آزادشده، $CX$ به‌عنوان یک کران پایین برای مقدار جواب بهینه برای برنامه‌ریزی عددصحیح اصلی است.\\
اگر یکی از متغییرها در $X$ صحیح نباشد، مثلا $x_j=r$، آنگاه روش شاخه و کران به صورت زیر پیش خواهد رفت. مسئله برنامه‌ریزی عددصحیح با اضافه کردن دو محدودیت جامع و منحصر به فرد از دو طرف، به دو زیرمسئله تقسیم می‌شود. در یکی از زیرمسئله‌ها به‌نام  $SP(1)$ برنامه‌ریزی عددصحیح اصلی با اضافه کردن محدودیت اضافی
\begin{equation*}
x_j\leq \lfloor r \rfloor ,
\end{equation*}
که $r$ نشان‌دهنده‌ی بزرگترین عدد صحیح کوچکتر از $r$ است، و در زیرمسئله بعدی به نام$SP(2)$   برنامه‌ریزی عددصحیح اصلی با اضافه کردن محدودیت اضافی
\begin{equation*}
x_j \geq \lceil r \rceil ,
\end{equation*}
که $r$ نشان دهنده‌ي کوچکترین عدد صحیح بزرگتر از $r$ است. واضح است که جواب بهینه‌ی برنامه‌ریزی عدد صحیح در یکی از  نواحی شدنی دو زیرمسئله قرار خواهد گرفت.\\روش شاخه و کران $LP‌$ آزاد شده  یکی از زیرمسئله ها را در نظر می‌گیرد و آن را حل می‌کند(مثلا $SP(1)$). اگر جواب به‌دست آمده صحیح بود،‌ آنگاه در این شاخه از درخت نیازی به پیشروی بیشتر نیست واین جواب بهینه‌ی مسئله عدد صحیح اصلی خواهد بود. اگر جواب به‌دست آمده صحیح نباشد آنگاه $SP(1)$ باید به دو زیرمسئله تقسیم شود و $SP(1,1)$ و $SP(1,2)$ نامیده می‌شود که محدودیت‌های جامع و منحصربه‌فرد از دو طرف عدد به‌دست آمده می‌باشند.\\
با پیش رفتن در این روش یک درخت ساخته می‌شود. از هرگره که به یک حل غیر صحیح مربوط می‌شود، از آن گره به دو گره دیگر وصل می‌شود و به همین ترتیب ادامه می‌یابد. روش محدود کردن آسان است. اگر در گره یک جواب غیرصحیح به‌دست آید، آنگاه این مقدار یک کران پایین برای همه‌ی جواب ها در شاخه‌ها فراهم می‌کند. در روش شاخه و کران هرگاه در گره‌های درخت عدد صحیح به‌دست آمد یا جواب غیرصحیحی که از جواب صحیح گره‌های دیگر بدتر بود به دست آمد، آن‌گاه روش شاخه و کران  متوقف می‌شود. گره با بهترین حل عدد صحیح به عنوان جواب بهینه برای مسئله عدد صحیح درنظر گرفته می‌شود.\\
تحقیقات زیادی در مورد تکنیک های روش شاخه و کران انجام شده است. تکنیک شاخه زدن همانند تکنیک محدود کردن نسبتا ساده است. چندین روش پیشرفته در استفاده از شاخه و کران که در عمل بسیار کاربرد دارند به اثبات رسیده اند، مثل
\begin{enumerate}[\hspace*{1em}$i$]
\item   آزادسازی ضریب لاگرانژ 
\vspace*{-3.8mm}
\item شاخه و کران
\vspace*{-3.8mm}
\item  شاخه و ارزش( اغلب به تولید ستون اشاره دارد) 
\end{enumerate}
روش آزادسازی ضریب لاگرانژ  یک تکنیک پیچیده برای تولید شاخه‌های کمتر در یک روش شاخه و کران است. این روش کران‌های پائین‌تر تولید می‌کند که اساساً بهتر از کران روش آزادسازی لاگرانژ که در بالا توضیح داده شد هستند و اساساً کران‌های بهتری در کل زمان محاسبه تولید می‌کنند. روش آزادسازی لاگرانژ به جای حذف محدودیت‌های صحیح، برخی از محدودیت‌های اصلی را آزاد می‌کند. اگرچه محدودیت‌های آزاد‌شده کاملا تقلیل یافته نشده‌اند. در عوض، برای جلوگیری از خطا، در تابع هدف با ضریب مناسب وزن‌دهی می‌شوند.\\
شاخه و برش دسته‌ای از روش‌هایی است که برپایه‌ی یک ترکیب از شاخه و کران با تکنیک صفحه‌ برش می‌باشد. شاخه و برش در هر زیرمسئله‌ از شاخه کردن درخت، یک الگوریتم صفحه برش برای ایجاد یک کران پایئن استفاده می‌کند. که الگوریتم صفحه برش در فرمول‌کردن مسئله‌هایی که شامل محدودیت‌های اضافی در گره می‌شود مورد استفاده قرار می‌گیرد. \\
روش شاخه و برش، ترتیبی از آزادسازی برنامه‌ریزی خطی مسئله با برنامه‌ریزی عددصحیحی که بایستی حل شود را حل می‌کند. روش مسئله برش، آزادسازی مسئله برای تقریب نزدیک درمسئله برنامه‌ریزی عددصحیح را بهبود می‌بخشد و شاخه و کران برای حل مسئله با استفاده از رویکرد تقسیم و موفقیت گام بر می‌دارد. یک رویکرد شاخه و کران محض به سرعت می‌تواند با به‌کارگیری برنامه صفحه برش، بیشتر در بالای درخت و یا در هر گره از درخت مورد توجه قرار گیرد. اخیرا این تکنیک‌ها در مسائل توزیع کامیون‌ها و زمان‌بندی خدمه مورد استفاده قرار گرفته است.\\
شاخه و ارزش اغلب برای حل مسائل عدد صحیحی استفاده می‌شود که تعداد زیادی متغییر(ستون) دارد. یک الگوریتم شاخه و ارزش همواره با یک مسئله محدود شده کار می‌کند که فقط یک زیرمجموعه از محدودیت‌ها محاسبه شده است. متغییرهای بیرونی مجموعه با صفر ثابت شده‌اند و ستون‌ها نظیر به نظیر نادیده گرفته می‌شوند. در یک نظریه‌ی برنامه‌ریزی خطی مشخص است که بعد از حل این مسئله محدود شده به منظور بهینگی، هر متغییر شامل یک صرفه‌جویی بالقوه منفی یا هم ارز و یک صرفه جویی مثبت که هزینه کاهش یافته نامیده می‌شود، می‌باشد. اگر متغییری که در مسئله محدود شده است شامل یک‌ صرفه‌جویی بالقوه منفی نشود، آنگاه یک جواب بهینه برای مسئله اصلی یافت می‌شود. با این حال، اگر متغییرهایی با یک صرفه‌جویی بالقوه مثبت وجود داشته باشد، آنگاه یکی یا بیشتر از این متغییرها باید در مسئله تقلیل یافته شامل شود. ایده‌ی اصلی در عقبه‌ی ایجاد ستون است که وقوع متغییرها با صرفه‌جویی بالقوه‌ی مثبت با شمردن همه‌ی متغییرها مشخص نمی‌شود، بلکه با حل یک مسئله بهینه‌سازی مشخص می‌شود. این مسئله بهینه‌سازی، مسئله ارزش نامیده می‌شود و به‌عنوان یک مسئله از یافتن متغییر با حداکثر صرفه‌جویی بالقوه (یا حداقل هزینه‌ی تقلیل یافته) تعریف می‌شود. برای اعمال ستون به طور موثر، مهم است که یک روش خوب برای حل مسئله ارزش بیابیم. یک الگوریتم شاخه و کران که کران‌های پائین‌تر با حل $LP$ آزادشده در طی ایجاد ستون محاسبه شده‌اند، یک الگوریتم شاخه و ارزش نامیده می‌شود. شاخه و ارزش و شاخه و برش در مسائل متنوع زمان‌بندی چندماشینی موازی با موفقیت به کار برده شده‌اند.\\
\section{مثال‌هایی از کاربردهای شاخه و کران}
در این قسمت کاربرد مسئله شاخه و کران را با دو مثال نشان می‌دهیم. ابتدا یک ماشین و $n$ فعالیت را درنظر بگیرید. فعالیت $j$ در تاریخ $r_j$ و در طی زمان $d_j$ انجام می‌شود. هدف حداقل کردن دیرکردهای غیر پیشدستانه است. این مسئله یک مسئله‌ی $NP-hard$ است. این مسئله یک مهم است زیرا پی در پی به عنوان یک زیرمسئله در روش‌های ابتکاری برای برنامه‌ریزی چیدمان و جریان کارگاهی نمود پیدا می‌کند( به عنوان مثال، روال تغییر مکان گلوگاه را در فصل 5 ملاحظه کنید). در یک تعداد از روش‌های شاخه و کران موثر و منطقی، توجه قابل ملاحظه‌ای را نسبت به خود جلب کرده است.\\
یک روش شاخه و کران برای این مسئله به‌صورت زیر می‌تواند تعریف شود. روش شاخه زدن ممکن است بر پایه‌ی حقیقتی باشد که برنامه‌ریزی‌ها در شروع زمان‌بندی بسط داده شوند. یک تک گره در سطح 0 که در بالاترین نقطه‌ی درخت است واقع می‌شود. در این گره هیچ‌یک از فعالیت‌ها در موقعیت‌های توالی قرار نگرفته‌اند. $n$ شاخه به سمت پایین به $n$ گره در سطح 1 وصل می‌شوند. هر گره در این سطح به یک بخشی از جواب با یک فعالیت خاص در اولین موقعیت زمان‌بندی مربوط می‌شود. همچنین در هر یک از این گره‌ها، $n-1$ زیرگره وجود دارد که هنوز در از لحاظ زمانی تعیین موقعیت نشده‌اند. $n-1$ کمان از هر گره در سطح 1 به سطح 2 جاری می‌شود.بنابراین $n\times (n-1)$ گره در سطح 2 وجود خواهد داشت. در هر گره در سطح 2، دو فعالیت در دو موقعیت اول مشخص شده‌اند. در سطح
$k$،
$k$ فعالیت‌ اول تثبیت شده‌اند.\\
اغلب لازم نیست که هر فعالیت باقی‌مانده را به عنوان یک کاندیدا برای موقعیت بعدی درنظر بگیریم. اگر در یک گره در سطح $k-1$، فعالیت‌های $j_1, ..., j_n$ در $k-1$ موقعیت اول تخصیص یابند، فعالیت $c$ بایستی به عنوان یک کاندیدا برای موقعیت $k$ام در نظر گرفته شود، اگر و فقط اگر
\begin{equation*}
r_c<\min_{l\in J} \Big (max(t,r_l)+p_l\Big),
\end{equation*}
که $j$ نشان‌ دهنده‌ی مجموعه‌ای از فعالیت‌هایی است که هنوز زمان‌بندی نشده‌اند و $t$ نشان دهنده‌ی زمانی است که ماشین فعالیت $j_{k-1}$ را تمام کرده و برای انجام فعالیت بعدی آزاد شده است. اگر فعالیت $c$ این نامعادله بالا را ارضا نکند، یعنی نامعادله به صورت زیر باشد، آنگاه
\begin{equation*}
r_c\geq \min_{l\in J} \Big (max(t,r_l)+p_l\Big),
\end{equation*}
که این احساس به‌ وجود می‌آید که فعالیت طوری قرار گیرد که $R.H.S$ را در موقعیت $k$ و فعالیت $c$ در موقعیت $k+1$ حداقل کند. در هر صورت تاثیری بر زمان تکمیل فعالیت $c$ نخواهد داشت. همچنین در این مورد، فعالیت $c$ نباید برای موقعیت $k$ درنظر گرفته شود.
\begin{figure}
\centering 
\includegraphics[scale=0.8]{01}
\caption{درخت شاخه و کران}
\end{figure}
چندین طرح محدودکردن برای تولید کران‌های کمتر برای گره‌ها، در درخت جستجو، وجود دارد. یک کران پایین آسان برای یک گره در سطح $k-1$ می‌تواند با برنامه‌ریزی $j$ شغل باقی‌ مانده مطابق با قانون پیش‌دستانه زودترین موعد تحویل ایجاد شود. قانون پیش‌دستانه‌ی زودترین موعد تحویل برای این مسئله خاص وقتی که پیشگیری مجاز باشد بهینه می‌شود و بنابراین یک کران پایین برای مسئله غیرپیش‌دستانه مهیا می‌کند. اگر یک قانون زودترین موعد تحویل پیش‌دستانه یک زمان‌بندی غیرپیش‌دستانه را به‌دست بیاورد، آنگاه همه‌ی گره‌ها با کران پایین بیشتر، می‌توانند نادیده گرفته شوند.\\
\textbf{مثال ب 1.4 (زمان‌بندی تک ماشینی)}
یک ماشین با 4 فعالیت زیر را درنظر بگیرید.\\
\begin{center}
\addtolength{\tabcolsep}{7pt}
\begin{tabular}{111111}
\hline فعالیت‌ها &1&2&3&4\\ \hline $p_j$ &4&2&6&5\\  $r_j$  &0&1&3&5\\ $d_j$ &8&12&11&10\\ \hline
\end{tabular}
\end{center}
هدف حداقل کردن حداکثر تاخیر $L_{max}$ است. در سطح 1 درخت جستجو، چهار گره (*,*,*,1)، (*,*,*,2)، (*,*,*,3)، (*,*,*,4) وجود دارند. به‌سادگی می‌دانیم که گره‌های (*,*,*,3) و (*,*,*,4) در اولین فرصت ممکن است نادیده گرفته شوند. فعالیت 3 در زمان 3 شروع می‌شود. اگر فعالیت 2 بخواهد کارش را در زمان 1 شروع کند، فعالیت 3 هنوز هم می‌تواند در زمان 3 شروع شود. فعالیت 4 در زمان 5 می‌تواند شروع شود، اگر فعالیت 1 بخواهد کارش را در زمان 0 شروع کند، فعالیت 4 هنوز هم می‌تواند در زمان 5 شروع شود (شکل ب.1 را ملاحظه کنید).\\
محاسبه‌ی یک کران پایین برای گره (*,*,*,1) مطابق با قانون زودترین موعد تحویل پیش‌دستانه یک زمان‌بندی به این صورت به‌دست می‌آید که فعالیت 3 در طی زمان [4,5]، فعالیت 4 در طی زمان [5,10]، فعالیت 3(دوباره) در مدت زمان [10,15] و فعالیت 2 در مدت زمان [15,17] کار خودشان را انجام می‌دهند.$L_max$  در این زمان‌بندی، کران پایینی را برای گره (*,*,*,1) نتیجه می‌دهد که مقدار آن 5 است. به‌ طریق مشابه یک کران پایین برای گره (*,*,*,2)، می‌توان به‌دست آورد. ارزش کران پایین برای این گره 7 می‌باشد.\\
گره (*,*,2,1) در سطح 2 را درنظر بگیرید. کران پایین برای این گره 6 می‌باشد و با زمان‌بندی (غیرپیش‌دستانه) 1و2و4و3 به‌دست می‌آید. گره (*,*,3,1) را در سطح 2 دنبال کنید. کران پایین 5 به‌دست می‌آید و با زمان‌بندی (غیرپیش‌دستانه) 1و3و4و2 تعیین می‌شود. برای گره (*,*,*,1) کران پایین 5 و برای گره (*,*,*,2) که در توالی زمان‌بندی 1و3و4و2 به‌دست آمد، بیشتر از عدد 5 می‌باشد.\\
مسئله کلی با موضوع فعالیت‌ها به منظور محدودیت‌های اولویت‌دار به صورت مشابه می‌توانند انجام شوند. ازآنجایی که مسئله محدودیت‌های بدون اولویت یک مورد خاص از مسئله با محدودیت‌های اولویت‌دار است، دومی از نقطه‌ نظر پیچیدگی حداقل از نوع مسائل $hard$ است. با این حال از نظر شمارشی، مسئله محدودیت‌های اولویت‌دار در واقع تاحدودی ساده‌تر از مسئله با محدودیت‌های بی‌اولویت است. زمان‌بندی‌هایی که محدودیت‌های اولویت‌دار را نقض می‌کنند می‌توانند به‌سرعت رد شوند. این موضوع موجب کاهش تعداد زمان‌بندی‌هایی که باید درنظر گرفته شوند، می‌شود.\\
این مسئله زمان‌بندی تک ماشینی غیرپیش‌دستانه با تاریخ‌های آزادی، موعدهای مقرر، محدودیت‌های اولویت‌دار و حداکثر هدف تاخیر، یک مسئله‌ی زمان‌بندی بسیار مهم به شمار می‌رود. زیرا مسائل زمان‌بندی چیدمان کارگاهی اغلب به‌گونه‌ای تجزیه می‌شوند که در فرایند جواب بسیاری از مسائل تک ماشینی از این دست باید حل شوند. (جابه‌جایی ابتکاری گلوگاه فصل 5 را نگاه کنید).\\
دومین مثال از کاربرد روش شاخه و کران مربوط به چیدمان کارگاهی است که در فصل 5 شرح داده شد. شاخه کردن همانند روش محدود کردن، در مسئله چیدمان کارگاهی که به نوعی یک طراحی خاص است کاربردی است. به منظور شرح یکی از روش‌های شاخه کردن، خودمان را به یک دسته از زمان‌بندی‌های خاص محدود می‌کنیم.\\
\textbf{تعریف 1(زمان‌بندی فعال).}
یک زمان‌بندی شدنی را فعال نامند، هرگاه به هیچ طریقی نتواند بهبود یابد، که برخی از عملیات‌ها زودتر انجام شود و سایر عملیات‌ها را نتوان بعداً تکمیل کرد.\\
یک برنامه‌ریزی فعال به این معنی است که وقتی یک فعالیت به یک ماشین می‌رسد، این فعالیت در اسرع وقت مطابق با توالی مقرر انجام شود. به منظور درک بهتر زمان‌بندی‌های فعال، زمان‌بندی غیرفعالی که در شکل ب.2 به تصویر کشیده شده است را درنظر بگیرید. در این زمان‌بندی غیرفعال یک دوره بیکاری بین فرایند دو عملیات وجود دارد و این زمان بیکاری به اندازه‌ی کافی بزرگ است که می‌توان فعالیتی را که برای انجام فرایند در زمان مقرر منتظر است را در آن گنجاند. این زمان‌بندی به طور واضح غیرفعال است. این بدین معنی است که یک زمان‌بندی فعال نمی‌تواند هیچ زمان بیکاری در عملیاتی از یک فعالیت منتظر زمان‌بندی داشته باشد.\\
مطابق تعریف، یک زمان‌بندی فعال خاصیتی دارد که این امکان را می‌دهد که دوره را بدون جلو بردن تاریخ شروع بعضی از فعالیت‌ها، می‌توان کاهش داد. البته زمان‌بندی‌های فعال مختلف فراوانی وجود دارد. می‌توان نشان داد که یک زمان‌بندی فعال وجود دارد که در میان همه‌ی برنامه‌ریزی‌های ممکن، بهینه است.\\
یک رویه شاخه کردن اغلب برپایه‌ی ایجاد همه‌ی برنامه‌ریزی‌های فعال است. تمامی این زمان‌بندی‌ها می‌توانند توسط یک الگوریتم ساده ایجاد شوند. در این الگوریتم $\Omega$ نشان دهنده مجموعه‌ای از تمام فعالیت‌هایی است که همگی آنها قبلاً برنامه‌ریزی شده‌اند. (یعنی، مجموعه‌ی همه‌ی عملیات‌های قابل زمان‌بندی) و $r_{ij}$ زودترین زمان ممکن شروع فعالیت $(i,j)$ در $\Omega$ است. مجموعه $\Omega'$ یک زیر مجموعه از مجموعه $\Omega$ است.\\
\begin{figure}
\centering 
\includegraphics[scale=0.9]{02}
\caption{یک زمان‌بندی غیرفعال}
\end{figure}
\textbf{الگوریتم ب.2.4 (ایجاد همه‌ی زمان‌بندی‌های فعال)}\\
گام 1. (شرایط اولیه)\\
\footnotesize
\hspace*{3mm}\emph{
$\Omega$ را اولین عملیات از هر فعالیت قرار دهید.\\
\hspace*{3mm}
برای همه‌ی ($i,j\in \Omega$)، $R_i,j=0$}\\     [3mm]
\normalsize
گام 2. (انتخاب ماشین)\\
\footnotesize
\hspace*{3mm}\emph{
زمان‌بندی جزیی فعلی را محاسبه کنید}\\[-7mm]
\normalsize
\begin{equation*}
t(\Omega)=\min_{(i,j)\in \Omega} \{r_{ij}+p_{ij}\}
\end{equation*}\footnotesize
\hspace*{3mm}\emph{و $i^*$ ماشینی را نشان دهد که حداقل را به‌دست آورده باشد.}\\[3mm]
\normalsize
گام 3. (شاخه زدن)\\
\footnotesize
\hspace*{3mm}\emph{$\Omega'$ مجموعه‌ای از تمامی عملیات‌های $(i^*,j)$ در ماشین $i^*$ قرار دهید به‌طوریکه }\\[-7mm]\normalsize
\begin{equation*}
R_{i^*j}<t(\Omega)
\end{equation*}
برای هر عملیات در $\Omega'$ یک زمان‌بندی جزیی (گسترش یافته) با عملیاتی که به عنوان عملیات بعدی در ماشین $i^*$ است درنظر بگیرید.\\
برای هر زمان‌بندی جزیی، عملیاتی که در مجموعه $\Omega$ است را پاک کنید و $\Omega$ را به روز کنید و به گام 2 بروید.
\begin{figure}
\centering 
\includegraphics[scale=0.7]{10}
\caption{درخت شاخه‌ای برای روش شاخه  و‌ کران}
\end{figure}
الگوریتم ب 3.4 پایه و اساس روش شاخه‌زدن است. گام 3، از گرهی که با زمان‌بندی جزئی داده شده مشخص شده است، شاخه می‌زند. تعداد شاخه‌ها برابر با عملیات‌ها درمجموعه‌ $\Omega'$ است. با استفاده از این الگوریتم می‌توان کل درخت و گره‌های آن در پایین درخت، مربوط به همه زمان‌بندی‌های فعال را ایجاد کرد.\\
بنابراین گره $4$ در درخت مربوط به یک برنامه‌ریزی جزئی است و برنامه‌ریزی جزئی با انتخاب کمان‌های منفصل که به ترتیب در همه گره‌های پیشین گرفته شده از مجموعه $\Omega$ برنامه‌ریزی شده‌اند، مشخص می‌شود. شاخه‌ خروجی از گره $V$ به انتخاب از یک عملیات $(i^*,j)\in \Omega'$ به رفتن به ماشین  $i^*$بعدی مربوط است. کمان‌های منفصل $(I^*,j)$ به $(i^*,k)$ برای همه فعالیت‌های $(i^*,k)$ که بر روی ماشین $i^*$ زمان‌بندی نشده‌اند باید به ماشین  $i^*$اضافه شود. این بدین معنی است که گره به تازگی ایجاد شده در سطح پایین‌تر $V'$ می‌گوییم که به یک زمان‌بندی جزئی با فقط یک زمان‌بندی عملیات اضافی مربوط است و شامل تعدادی از کمان‌های منفصل انتخاب شده اضافی  است (شکل ب.3 را ببینید). $D'$ نشان‌دهنده‌ی مجموعه‌ای از کمان‌های منفصل انتخاب شده در گره‌های تازه تولید شده است. به گراف با کمان‌های منفصل و مجموعه $D'$ به عنوان گراف $G(D')$ توجه کنید. تعداد جوانه‌زدن شاخه‌ها از گره $V$ برابر است با تعداد عملیات‌ها در$\Omega'$.\\
برای یافتن یک کران پایین برای بازه در گره $V'$ گراف $G(D')$ را در نظر بگیرید. طول مسیر بحرانی در این گراف درحال حاضر در یک کران پایین برای بازه گره $V'$ به دست می‌آمد. این کران پایین را $LB(V')$ بنامید. کران‌های پایین بهتری برای این گره به‌‌صورت زیر می‌توانند به‌دست آیند.\\
ماشین $i$ را در نظر بگیرید و فرض کنید که به تمام ماشین‌های دیگر در هر زمان و عملیات‌های چندگانه همزمان اجازه پردازش داده شود (چون همه کمان‌های منفصل در گراف $g(D')$ هنوز انتخاب نمی‌شوند و ممکن است که، در بعضی از زمان‌ها عملیات‌های چندگانه نیازمندپردازش بر روی یک ماشین به‌طور همزمان داشته باشند). با این حال ماشین $i$ را برای پردازش عملیات‌هایش یکی پس از دیگری به کار می‌گیریم. ابتدا زودترین زمان شروع ممکن $r_{ij}$ برای همه عملیات‌های عملیات‌های $(i,j)$ ماشین $i$ محاسبه می‌کنیم، که این گراف در $G(D')$ طول بزرگترین مسیر از منبع به گره $(i,j)$ تعیین می‌کند. سپس برای هر عملیات $(i,j)$ بر روی ماشین $i$ حداقل مقدار زمانی موردنیاز بین تکمیل عملیات $(i,j)$ و کران‌ پایین $LB(V')$، با تعیین کردن بزرگترین مسیر از گره $(i,j)$ به مخزن گراف $G(D')$ محاسبه می‌کنیم. این مقدار زمان و به همراه آن کران پایین دوره ساخت، به یک موعد مقرر $d_{ij}$ برای عملیات $(i,j)$ بیان می‌کند. یعنی $d_{ij}$ برابر با $LB(V')$ منهای طول بزرگترین مسیر از گره $(i,j)$ تا مخزن بعلاوه $p_{ij}$. اکنون مسئله‌ی توالی عملیات بر روی ماشین $i$ را به عنوان مسئله تک ماشینی با فعالیت‌های آزادشده در زمان‌های مختلف را درنظر بگیرید. هیچ پیش‌دستی مجاز نیست و حداکثر تاخیر به‌عنوان هدفی برای حداقل کردن است. (این مسئله‌ای است که در بخش 5.2 توضیح داده شد). هرچند این مسئله یک مسئله $NP-hard$ است، ولی الگوریتم‌های نسبتا سریعی وجود دارند که جواب‌های بسیار خوبی را به‌دست می‌آورند. توالی بهینه‌ی به‌دست آمده برای این مسئله، یک انتخاب از کمان‌های منفصل که می‌توانند به $D'$ (به‌طور موقت) اضافه شوند را اشاره می‌کند. این ممکن است به یک مسیر بحرانی بزرگتر سرتاسری در گراف و یک بازه بزرگتر  و یک کران پایین بهتر برای گره $\nu'$ منجر شود. در گره $\nu'$ برای هریک از $m$ ماشین به طور مجزا می‌تواند انجام شود. بزرگترین بازه  به دست آمده این روش می‌تواند به‌عنوان $\nu'$ درنظر گرفته شود. البته کمان‌های منفصل موقتی واردشده برای به دست آوردن کران پایین به محض مشخص شدن بهترین کران پایین حذف می‌شوند.\\
با وجود اینکه به نظر می‌رسد بخشی از حل $m$ مسئله زمان‌بندی $NP-hard$ برای به‌دست‌ آوردن یک کران پایین برای سایر مسائل $NP-hard$ است، اینگونه روش حل در عمل به خوبی اجرا می‌شوند.\\[3mm]
\textbf{مثال ب3.4‌(کاربردی از روش شاخه و کران) }
\\مثال توضیح داده شده در 5.2.1 را در نظر بگیرید. گراف اولیه شامل فقط کمان‌های ربط دهنده است و در شکل ب.4.$a$ به تصویر کشیده شده است. دوره ساخت مربوط به این گراف 22 است. با اعمال روش شاخه و کران در این مثال درخت شاخه و کران زیر را نتیجه می‌دهد.\\
\textit{مرحله1:}
با اعمال الگوریتم ب.4.3 نتایج زیر حاصل می‌شود.\\[-0.3cm]
\[
\begin{split}
\Omega & =\{(1,1), (2,2), (1,3)\}, \\
t(\Omega) & =min(0+10, 0+8, 0+4)=4, \\
i^* & =1,\\
\Omega' & =\{(1,1),(1,3)\}.
\end{split}
\]
\begin{figure}
\centering 
\includegraphics[scale=0.7]{hamid}
\caption{ترتیب اولوبت گراف‌ها در سطح 1 مثال ب.4.4}
\end{figure}
همچنین دو گره مورد نظر در سطح 1، یکی مربوط به عملیات (1و1) ابتدا روی ماشین 1 انجام می‌شود و دیگری عملیات (3و1) است که روی ماشین 1 انجام می‌شود.\\
اگر عملیات (1و1) ابتدا زمان‌بندی شود، آنگاه دو گره منفصل نشان داده شده در شکل ب.4.ب به گراف اضافه می‌شوند. گره با دو کمان منفصل زیر مشخص می‌شود.\\[-3mm]
\[
\begin{split}
(1,1) & \longrightarrow (1,2),\\[-2mm]
(1,1) & \longrightarrow (1,3),
\end{split}
\]
با اضافه شدن این دو کمان منفصل، کران پایین بلافاصله تا دوره ساخت 24 افزایش می‌یابد. به منظور بهبود این کران پایین می‌توان برای ماشین 1 نمونه از حداکثر مسئله تاخیر با آزادسازی تاریخ و موعد مقرر ایجاد کرد. تاریخ آزاد فعالیت j در این مسئله تک ماشینی با بزرگترین مسیر منبع تا گره $(1,j)$ در شکل ب.4.ب مشخص می‌شود. موعد مقرر فعالیت $j$ با یافتن بزرگترین مسیر از گره $(1,j)$ تا مخزن، تفاضل $p_{1j}$ از طول این بزرگترین مسیر و کم کردن مقدار حاصل از 24 محاسبه می‌شود. این محاسبات به مسئله تک ماشینی زیر برای ماشین 1 منجر می‌شود. 
\begin{center}
\addtolength{\tabcolsep}{2pt}
\begin{tabular}{11111}
\hline فعالیت‌ها &1&2&3\\ \hline $p_1j$ &10&3&4\\  $r_1j$  &0&10&10\\ $d_1j$ &10&13&14\\ \hline
\end{tabular}
\end{center}
توالی که $L_{max}$ را در این مسئله تک ماشینی حداقل می‌کند 1و2و3 با $L_{max}=3$ است. این بدین معنی است که یک کران پایین برای بازه ساخت در گره متناظر ۲۴+3=27 است. یک نمونه از حداقل کردن حداکثر مسئله تاخیرات مربوط به ماشین ۲ می‌تواند به روش مشابه انجام شود. تاریخ‌های آزادی و موعدهایی مقرر در شکل ب.4 و مطابق زیر هستند (با فرض بازه ساخت 24).
\begin{center}
\addtolength{\tabcolsep}{2pt}
\begin{tabular}{11111}
\hline فعالیت‌ها &1&2&3\\ \hline $p_2j$ &8&8&7\\  $r_2j$  &10&0&14\\ $d_2j$ &0&10&21\\ \hline
\end{tabular}
\end{center}
ترتیب بهینه 2و1و3 با $L_{max}=4$ است. این یک کران پایین‌تر برای دوره ساخت در گره مربوط به عملیات (1و1) ابتدا زمان‌بندی می‌شود، یعنی 28=4+24. با آنالیز ماشین‌های 3 و 4 به طریق مشابه یک کران پایین بهتر به دست نمی‌آید.\\ 
گره دوم در سطح 1 مربوط به عملیات (3و1) ابتدا زمان‌بندی می‌شود. اگر (3و1) ابتدا زمان‌بندی شود، دو کمان منفصل متفاوت به گراف اصلی اضافه می‌شود و یک کران پایین با 26 به دست می‌آید. در ارتباط با مثال مسئله حداکثر تاخیرات برای ماشین 1 یک توالی بهینه 3و1و2 با $L_{max}=2$ دارد. این بدین معنی است که کران پایین برای بازه ساخت در این گره مربوط به عملیات (3و1) ابتدا زمان‌بندی می‌شود و برابر 28 است. با بررسی ماشین‌های2،3 و 4 کران پایین بهتری را به دست نمی‌آید. \\[2mm]
گام بعدی، شاخه زدن از گره (1و1) در سطح 1 است و گره‌هایی را در سطح بعدی ایجاد می‌کند.\\
\textbf{مرحله 2:}
اعمال کردن الگوریتم ب.4.3 به صورت زیر نتیجه می‌دهد.\\[-0.3cm]
\[
\begin{split}
\Omega & =\{(2,2), (2,1), (1,3)\}, \\
t(\Omega) & =min(0+8, 10+8, 10+4)=8, \\
i^* & =2,\\
\Omega' & =\{(2,2)\}.
\end{split}
\]
یک گره از بهره در این بخش از سطح 2 وجود دارد، گره مربوط به عملیات (2و2) روی ماشین 2 ابتدا انجام می‌شود (در شکل ب.5 ببینید). دو گره منفصل، به گراف یعنی (2و2) به (1و2) و (2و2) به (3و2) اضافه می‌شود. همچنین این گره با یک مجموعه از چهار کمان منفصل مشخص می‌شود.
\begin{figure}
\centering 
\includegraphics[scale=0.7]{07}
\caption{شاخه مثال ب.4.4}
\end{figure}
\vspace*{-1cm}
\[\begin{split}
(1,1) & \longrightarrow (1,2),\\[-2mm]
(1,1) & \longrightarrow (1,3),\\[-2mm]
(2,2) & \longrightarrow (2,1),\\[-2mm]
(2,2) & \longrightarrow (2,3),
\end{split}
\]
این به یک نمونه از مسئله حداکثر تاخیرات برای ماشین ۱ با تاریخ‌های آزادسازی موعدهای مقرر زیر منجر می‌شود.\\
\begin{center}
\addtolength{\tabcolsep}{2pt}
\begin{tabular}{11111}
\hline فعالیت‌ها &1&2&3\\ \hline $p_1j$ &10&3&4\\  $r_1j$  &0&10&10\\ $d_1j$ &14&17&18\\ \hline
\end{tabular}
\end{center}
توالی فعالیت بهینه 1و3و2 و $L__{max}=0$ است. این بدین معنی‌ است که کران پایین برای دوره ساخت در گره مربوطه 28=0+28 است. با بررسی ماشین‌های 2 و 3 و 4 به طریق مشابه، کران پایین را افزایش نمی‌دهد.\\ 
ادامه روش شاخه و کران در توالی فعالیت برای چهار ماشین به صورت زیر است.
\begin{center}
\addtolength{\tabcolsep}{5pt}
\begin{tabular}{11111}
\hline &توالی فعالیت ماشین\\ \hline 1 &1و3و2 (یا 1و2و3)\\  2  &2و1و3\\ 3 &1و2 \\ 4& 2,3 \\ \hline
\end{tabular}
\end{center}
\begin{figure}
\centering 
\includegraphics[scale=1]{09}
\caption{زمان‌بندی بهینه در مثال ب.4.4}
\end{figure}
دوره‌ی ساخت زیر این زمان‌بندی بهینه 28 است (شکل ب.6 را ببینید).\\
روش در بالا مبتنی بر شمارش کامل است و موجب تضمین یک زمان‌بندی بهینه می‌شود. با این حال با تعداد زیاد ماشین‌ها و تعداد زیاد فعالیت‌ها محاسبه‌ی زمان سخت است. در حال حاضر با 20 ماشین و 20 فعالیت، یافتن زمان‌بندی بهینه بسیار سخت خواهد بود. \\[2cm]
\Large
تمرین‌ها:\\[0.5cm]
\large
ب.1.
\normalsize
مثال درنظر گرفته شده در ب.2.2 را با استفاده از فرمول‌بندی برنامه‌ریزی پویای پسرو که در مثال ب.2.3 توضیح داده شد، حل کنید. \\[0.5cm]
\large
ب.2. 
\normalsize
مسئله چیدمان کارگاهی توضیح داده شده در تمرین 5.5 را درنظر بگیرید. مسئله شاخه و کران توضیح داده شده در بخش ب.4 را حل کنید.\\[2cm]
\Large
منابع:
\normalsize
\begin{center}
\includegraphics[scale=0.85]{11}
\end{center}
\end{document}