مقاله درمورد مقایسه نتایج و بهبود کیفیت


Widget not in any sidebars
شکل ‏21: نمودار گانت مثال جریان‌کارگاهی
همانگونه که در نمودار فوق دیده می شود، تابع هدف که عبارت است از زمان تکمیل آخرین کار ()، برای ترتیب داده شده 29 می‌باشد.
مرور ادبیات جریان‌کارگاهی
اولین مقاله در زمینه FS توسط آقای جانسون [1] در 1954 منتشر شد. از آن زمان تاکنون مقاله‌های متعددی در این زمینه در مجله‌های معتبر علمی به چاپ رسیده است. با وجود اینکه مفهوم مدل زمان‌بندی توسط آقای جانسون معرفی شده است، لیکن عنوان برای نخستین بار در 1965 در مقاله ایگنال و اسچارج [6] به کار گرفته شد. در 1996 هال و سریکاندراجا [7] ثابت نمودند که مساله جریان‌کارگاهی برای بیش از دوماشین یک مساله است. در سال 2006 گوپتا و همکاران [8] در مقاله خود مقاله‌های چاپ شده در این حوزه را به 5 دوره تقسیم کردند. بیشتر تحقیقات دوره اول مرتبط با مسائل ریاضی همان مدل اولیه آقای جانسون است و بیشتر روی 2 یا 3 ماشین بحث می‌نماید.
در دوره دوم بین 1965 تا 1974 شاهد ایجاد راه حل‌های متفاوت از یک سو و همچنین در نظر گرفتن توابع غیر از زمان کل از سوی دیگر بود. در این دوره موضوع عمده مقاله‌ها، ارائه روش‌های بهینه برای حل مسائل مختلف بود.
در دوره سوم به علت پیچدگی روش‌های بهینه، روش‌های ابتکاری متعددی برای حل این نوع مسائل ابداع گردند. در این دهه بود که مدل‌سازی احتمالی این نوع مسائل نیز مطرح گردید.
در دوره چهارم ( 1985 تا1994) مسائل زمان‌بندی ترکیبی مطرح گردید. در این دهه از انواع روش‌های فراابتکاری استفاده شده است. به علت استفاده از فرضیات مرتبط با زمان‌های مستقل و وابسته، هوش مصنوعی و سیستم‌های پشتیبان تصمیم‌گیری دوره چهارم را می‌توان پر فروغ‌ترین دوره تحقیقات مسأله زمان‌بندی جریان‌کارگاهی دانست.
در دوره آخر که تاکنون ادامه دارد شاهد تنوع مسأله، توابع هدف و ابداع روش‌های متفاوت بسیاری بوده‌ایم و پیوندها با دیگر مسائل برنامه ریزی تولید، در این دوره انجام گردیده است.
الگوریتم‌های ابتکاری
پیچیدگی حاصل از افزایش تعداد ماشین‌ها و کارها و عدم وجود روشهای دقیق برای آنها، محققان را به سمت استفاده و گسترش الگوریتم‌های ابتکاری سوق داده است. این موضوع مهم‌ترین دلیل وجود تعداد بالای الگوریتم‌های ابتکاری در ادبیات این موضوع می‌باشد. در ادامه مروری جامع بر الگوریتم‌های ابتکاری در حوزه جریان‌کارگاهی خواهیم داشت و خواهیم دید که الگوریتم‌های ابتکاری در این حوزه را می‌توان به‌طور کلی در سه الگوریتم جانسون، پالمر و تقسیم نمود و در انتها با این سه الگوریتم آشنا می‌شویم.
مروری بر الگوریتم‌های ابتکاری در حوزه جریان‌کارگاهی
الگوریتم جانسون [1] اولین الگوریتم شناخته شده برای مسأله جریان‌کارگاهی می‌باشد. با استفاده از این الگوریتم مقدار بهینه در حالتی که تنها دو ماشین وجود دارد، به دست آورده می‌شود. پیچیدگی این الگوریتم می‌باشد.
الگوریتم جانسون را می‌توان برای حالتی که در آن تعداد ماشین‌ها بیش از دو است تعمیم داد. در این زمینه الگوریتم‌های متعددی معرفی شده است. دودک و تئوتون [9] برپایه الگوریتم جانسون، قانونی m مرحله‌ای را استفاده کردند که مجموع زمان اتلاف روی آخرین ماشین در صورتی که پردازش هر کار از رویکرد جانسون انجام شود را کمینه می‌کرد. کمپل و همکاران [10] الگوریتمی را پیشنهاد نمودند که نیازمند m-1 مرحله محاسبات بود. در این الگوریتم هر m ماشین واقعی در هر مرحله به دو گروه ماشین مجازی افراز شده و سپس طبق الگوریتم جانسون محاسبات صورت می‌پذیرفت. پیچیدگی محاسباتی این الگوریتم می‌باشد. گوپتا [11] یک الگوریتم ابتکاری برای کمینه کردن زمان اتلاف به نام و دو الگوریتم ابتکاری برای کمینه‌کردن طولانی‌ترین زمان تکمیل به نام‌های و ارائه نمود. مقایسه نتایج بدست آمده نشان‌دهنده بهبود کیفیت و کاهش زمان حل نسبت به الگوریتم پیشنهادی کمپل بود.
در الگوریتم ابتکاری که توسط پالمر [12] پیشنهاد شده است، برای هر کار شاخصی معین می‌گردد و کارها براساس این شاخص زمان‌بندی می‌شوند. شاخص تعریف شده توسط پالمر نام دارد. پیچیدگی محاسبات این الگوریتم می‌باشد. بونی و گوندری [13] مجموع زمان‌های پردازش هر کار بر روی تمام ماشین‌ها را به عنوان معیار هرکار درنظر گرفته‌اند. هوندال و راجگوپال [14] با معرفی دو شاخص جدید و استفاده از شاخص پالمر سه زمان‌بندی برای هر مسئله معرفی نمودند. پیچیدگی محاسبات این الگوریتم، مشابه با الگوریتم پالمر می‌باشد. داننبریج [15] الگوریتمی ابتکاری براساس الگوریتم‌های ابتکاری جانسون و پالمر ارائه نمود. در این الگوریتم، مشابه با الگوریتم کمپل، ماشین‌ها به صورت ماشین‌های مجازی دوتایی فرض شده و سپس با استفاده از مقدارهای به‌دست آمده، شاخصی جهت هر کار تعیین می‌گردد.
نواز و همکاران [16] الگوریتم ابتکاری را ارائه کردند که این الگوریتم بهترین الگوریتم ارائه شده برای مسائل جریان‌کارگاهی می‌باشد. در این الگوریتم اولویت به کارهایی داده می‌شود که زمان پردازش بیشتری دارند. پیچیدگی محاسبات این الگوریتم O(n3m) می‌باشد. راجندران [17] الگوریتم ابتکاری به نام ارائه نمود که بسیار شبیه الگوریتم است که تنها تفاوت آن، در شرط اولیه برای بدست آوردن توالی اولیه می‌باشد. وی برای هر کار، مجموع زمان پردازش وزن‌داری را معرفی می‌کند.
سارین و لفوکا [18] الگوریتمی ابتکاری در نظر گرفتند که ایده‌ی آن کمینه کردن زمان اتلاف روی آخرین ماشین بود. این ایده باعث کاهش طولانی‌ترین زمان تکمیل می‌شود. در این الگوریتم، اولویت با کارهایی است که کمترین مجموع زمان پردازش روی همه‌ی ماشین‌ها را دارا هستند. مقایسه نتایج بدست آمده از این الگوریتم نسبت به الگوریتم در مسائلی با بیش از150کار بهتر است.
راجندران و زیگلر [19] الگوریتم ابتکاری ارائه نمودند که در آن در ابتدا به هر کار وزنی تخصیص داده می‌شد. سپس برای هر کار مجموع زمان پردازش وزن‌دار محاسبه شده و بر اساس مقادیر بدست آمده دو توالی نزولی و صعودی تعیین می‌گردد. از بین دو توالی، هر کدام که مقدار تابع هدف بهتری داشته باشد، به عنوان توالی اولیه انتخاب و سپس از الگوریتم استفاده می‌گردد.
وو و ییم [20] الگوریتمی ابتکاری مشابه با الگوریتم Raj ارائه نمودند. در الگوریتم ارائه شده نیازی به توالی اولیه نیست. در ابتدا مجموع زمان پردازش کارها محاسبه شده و سپس همانند الگوریتم و توالی بهینه بدست خواهد آمد. نتایج نشان می‌دهد که این الگوریتم برای تابع هدف کمینه‌کردن مجموع زمان جریان از الگوریتم های ، و کمپل بهتر عمل می‌کند. پیچیدگی محاسبات این الگوریتم O(n4m) می‌باشد.
حمید داوودپور [21] الگوریتمی مشابه با الگوریتم با هدف کمینه‌کردن حداکثر دیرکرد ارائه نمود. وی الگوریتم ارائه شده را روی 2000 مسأله مختلف با اندازه‌های مختلف تست نمود. مقایسه جواب‌های بدست آمده با الگوریتم های ، کمپل و پالمر نشان داد که این الگوریتم برای مسائلی با تعداد ماشین‌های بزرگ جواب‌های خوبی را بدست می‌آورد.
فرامین [22] نشان داد که الگوریتم که فقط برای مسائلی با تابع هدف طولانی‌ترین زمان تکمیل بکار می‌رفت، اگر برای مسائلی با تابع هدف کمینه‌کردن مجموع زمان جریان نیز به کار رود، بهترین جواب‌ها را در زمان‌های کمتر بدست می‌دهد. همچنین نشان می‌دهد که اگر الگوریتم برای توالی اولیه خود کارها را بر اساس مجموع زمان پردازش هر کار و به ترتیب صعودی قرار دهد یعنی اولویت با کارهایی باشد که مجموع زمان پردازش کمتری دارند، جواب‌های بهتری نسبت به اصلی بدست می‌آید.
الگوریتمی که توسط لاها و سارین [23] برای مسأله‌ای با تابع هدف کمینه‌کردن مجموع زمان جریان بر پایه الگوریتم ابتکاری ارائه شده بر پایه الگوریتم ابتکاری فرامین [22] است. تفاوت آن با الگوریتم فرامین آن است که پس از تعیین دو کار اول، کارهای بعد می توانند در هر کجای ترتیب بدست آمده قرار گیرند.
الگوریتم جانسون
الگوریتم جانسون اولین الگوریتم ارائه شده برای مسائل جریان‌کارگاهی است، که یک جواب بهینه برای به دست می‌آورد. این الگوریتم دارای پیچیدگی می‌باشد. جانسون مسئله کارگاه جریان دو‌ماشینه را با تابع هدف حداقل‌کردن طولانی‌ترین زمان تکمیل بررسی کرد و با ارائه الگوریتمی کارا توانست جواب بهینه این مسئله را با فرضیات پایه، به سادگی محاسبه نماید.
گام‌های الگوریتم جانسون را می‌توان به شرح زیر بیان نمود:
گام اول کارها را به دو گروه و تقسیم می‌کنیم بگونه‌ای که در گروه کارهایی قرار گیرند که برای آنها و در گروه کارهایی که برای آنها برقرار است. کارهایی که برای آنها است می‌توانند در هر دو گروه جای گیرند.
گام دوم کارهای موجود در گروه در ابتدا و به ترتیب صعودی قرار می‌گیرند ().