SPT

 

 

 

 

Traveling Saleman Problem

 

 

:

 

 

TSP

 

 

 

 

مقدمه
امروزه در عرصه صنعت بدلیل تفاوت و گوناگونی نیازهای مشتریان شاهد تنوع محصول‌ها، کوتاه شدن عمرشان و رقابت بالای تولیدکنندگان می‌باشیم. از این‌رو اهمیت به کارگیری روش‌هایی کارا جهت استفاده موثر از منابع بیش‌تر از گذشته نیاز می‌شود تا سازمان‌ها بتوانند قدرت پاسخگویی سریع به نیازهای مشتریان را داشته باشند. تکنیک‌های توالی عملیات و زمان‌بندی از جمله ابزار موثر در این رابطه است.
در ادامه این فصل، ابتدا مقدمه‌ای از اهمیت و ضرورت زمان‌بندی تولید و توالی عملیات گفته می‌شود و سپس با مفاهیم توالی عملیات و نمادگذاری انواع مختلف مسائل آشنا خواهیم شد.
توالی عملیات و زمان‌بندی
تعیین توالی‌کارها[1] و زمان‌بندی[2] به معنی تخصیص منابع محدود به فعالیتهایی است که به آن منابع نیاز دارند. از این‌رو می توان آن را نوعی فرایند تصمیم‌گیری دانست که با هدف بهینهسازی یک و یا چند هدف انجام میگیرد. این امر نقش بسیار مهمی در کاهش هزینه‌ها، افزایش بهره‌وری، افزایش رضایت مشتری و به طور کلی افزایش سودآوری شرکت‌ خواهد داشت.
آغاز علم زمان‌بندی را بدون شک باید در تلاش‌های هنری گانت[3] در دو دهه ابتدایی قرن بیستم جستجو کرد. اما شروع تحقیقات جدی و گسترده در این زمینه و مرتبط ساختن آن با تحقیق در عملیات به اوایل دهه 1950 بر می‌گردد. اولین الگوریتم زمان‌بندی که به صورت مستقیم مسائل زمان‌بندی را به تحقیق در عملیات مرتبط ساخت، در سال 1954 توسط جانسون [1] ارائه شد و تقریبا برای اولین بار جواب بهینه یک مسأله زمان‌بندی بوسیله آن بدست آمد. پس از آن مسائل متعددی در زمینه توالی عملیات معرفی و الگوریتم‌های متنوعی برای حل آنها توسعه داده شد.
در مسأله زمان‌بندی موجود در سیستم‌های صنعتی (خدماتی)، با یک سری از منابع، عمدتا ماشین‌ها و یک تعداد کار که باید بر روی (از) این ماشین‌ها (خدمت دهنده‌ها) پردازش شوند (خدمت بگیرند) و یک سری از محدودیت‌ها سروکار داریم که با توجه به آنها در صدد بهینه کردن یک یا چند تابع هدف هستیم.
شاخه‌ای از علم توالی عملیات به نام زمان‌بندی جریان‌کارگاهی[4] نامیده می شود. زمان‌بندی جریان‌کارگاهی یکی از مدل‌های سنتی زمان‌بندی و توالی عملیات است که طیف وسیعی از مسائل عملی زمان‌بندی را در خود جای می‌دهد. در مدل جریان‌کارگاهی تعدادی کار و ماشین وجود دارد که این کارها هر یک با مسیر یکسان باید بر روی تمام ماشین‌ها پردازش شوند. در این مدل، عملیات هر کار به ترتیب بر روی ماشین اول، ماشین دوم و تا ماشین آخر انجام می‌گردد و همچنین هر ماشین فقط یک کار را در هر زمان انجام می‌دهد و هدف انجام تمامی کارها با کمترین هزینه می‌باشد. در واقع در مدل جریان‌کارگاهی جریان پیوسته‌ای از کارها وجود دارد که بایستی توسط چند ماشین پردازش شوند و به همین دلیل به نام جریان‌کارگاهی نامیده می‌شود.
آشنایی با مفاهیم زمان‌بندی
منابع و کارها در یک سازمان می‌توانند صورت‌های مختلفی داشته باشند. برای نمونه، منابع می‌توانند ماشین‌های یک کارگاه، باندهای پرواز در یک فرودگاه، خدمه‌ها در یک محل احداث بنا و یا واحدهای پردازش در یک محیط محاسباتی باشند. همچنین کارها می‌توانند عملیات در یک فرایند تولیدی، بلند شدن و نشستن هواپیما در یک فرودگاه، مراحل یک پروژه تولیدی و یا اجرای برنامه‌های رایانه‌ای باشند. هر کار نیز می‌تواند دارای یک سطح اولویت یا اهمیت خاص، زودترین زمان ممکن برای شروع پردازش و یک موعد تحویل باشد. تابع هدف نیز می‌تواند به صورت‌های مختلف تعریف شود. برای نمونه تابع هدف می‌تواند کمینه کردن زمان اتمام پردازش آخرین کار و یا کمینه کردن تعداد کارهایی که پردازش آنها بعد از موعد تحویلشان به پایان می‌رسد، باشد [2].
در ادامه این قسمت در ابتدا با نمادگذاری مسائل زمان‌بندی آشنا خواهیم شد و پس از آن پیچیدگی مسائل زمان‌بندی مورد بحث قرار خواهد گرفت.
نمادگذاری
به دلیل تنوع مدلهای زمانبندی و توالی‌عملیات و به منظور تفکیک مناسب این مسائل از یکدیگر چنیدن روش نمادگذاری معرفی شده است. برای اولین بار کانوی و همکاران[3] از یک نمادگذاری 4 تایی بصورت برای مسائل زمان‌بندی استفاده نمودند. با این‌حال نمادگذاری که امروزه از آن استفاده می‌شود نخستین بار توسط گراهام و همکاران [4] در 1979 معرفی شده است. در این شیوه، یک مسأله زمان‌بندی با یک 3 تایی نشان داده میشود که قسمت α محیط ماشینها[5] را توصیف میکند و فقط شامل یک نماد است. قسمت β خصوصیات پردازش و محدودیتهای موجود را شرح می‌دهد که این قسمت میتواند شامل هیچ نماد و یا چند نماد باشد. قسمت تابع(های) هدفی که باید بهینه شود را توصیف میکند. لازم به ذکر است که این نمادگذاری بعدها توسط پیندو [2] به‌روز شده است. در ادامه به مقادیر مختلفی که هر کدام از اجزای این نمادگذاری می توانند داشته باشند، خواهیم پرداخت و در پایان برای روشن شدن موضوع چندین مثال معرفی خواهد شد.
حالتهای مختلف محیط ماشینها
در دنیای واقعی انواع گوناگونی از محیطهای تولیدی و خدماتی شامل تک ماشینه، ماشینهای موازی، جریان‌کارگاهی، کار کارگاهی و کارگاه باز به شرح زیر وجود دارد. نماد مرتبط با هر مشخصه در مقابل آن در داخل پرانتز آورده شده است.
محیط تک ماشینه[6] (1): در محیط تک ماشینه همانطور که از نام آن پیداست یک ماشین وجود دارد که تعدادی کار به وسیله‌ی این ماشین پردازش می‌شوند.
شکل ‏1‑1: شمایی از محیط تک ماشینه
محیط جریان‌کارگاهی (Fm): دریک محیط جریان‌کارگاهی، n کار برروی m ماشین به ترتیب پردازش میشوند. در این محیط توالی پردازش کارها بر روی ماشینهای مختلف یکسان است. به عبارت دیگر، همه کارها ابتدا روی ماشین اول، سپس روی ماشین دوم و به همین ترتیب تا ماشین m ام پردازش می‌شوند. پس از اتمام پردازش یک کار روی یک ماشین، آن کار به صف پردازش ماشین بعدی می‌پیوندد. اغلب فرض میشود که تمامی صفها بر اساس قانون [7] کار میکنند، یعنی هیچ کاری نمیتواند از کار دیگری که در صف انتظار است سبقت بگیرد. شمایی از محیط جریان‌کارگاهی، در شکل زیر نشان داده شده است. در این شکل، نشان دهنده ماشین ام کارگاه بوده و نیز نشان دهنده‌ی ظرفیت فضای قبل از ماشین iام است. صف کارها برای پردازش روی هر ماشین در فضای قبل از آن ماشین شکل میگیرد. ظرفیت فضای قبل از هر ماشین میتواند هر عددی از صفر تا بی‌نهایت باشد.
شکل ‏1‑2: شمایی از محیط جریان‌کارگاهی
محیط جریان‌کارگاهی انعطاف پذیر[8] (FFc) : در شرایطی که در یک محیط جریان‌کارگاهی در برخی از ایستگاهها بیش از یک ماشین برای پردازش کارها وجود داشته باشد، به این محیط، محیط جریان‌کارگاهی انعطافپذیر گفته می‌شود. در این محیط، کار تنها با شروع از ایستگاه اول پردازش میشوند و برای پردازش آنها تا ایستگاه ام ادامه خواهد داشت. در این محیط هر کار تنها توسط یکی از ماشینهای موازی هر ایستگاه پردازش میشود. در شکل زیر شمایی از محیط جریان‌کارگاهی انعطاف پذیر، نشان داده شده است.
شکل ‏1‑3: شمایی از محیط جریان‌کارگاهی انعطاف پذیر
محیط کار کارگاهی[9] (Jm): یک کارگاه با شیوه تولید کار کارگاهی از آرایش یک سری ماشین‌آلات با استفاده عام که مورد استفاده یک حرفه خاص هستند، پدید میآید. مثلا یک سری ماشین‌آلات تراش، فرز، دریل، آهنگری و … تولید هر یک از محصولات در این شیوه با تولید محصول دیگر متفاوت است و هر یک نیاز به طی مسیر تولیدی خاص خود را دارند.
کارگاه باز[10] (Om): در این حالت ماشین وجود دارد و هر کار باید حداقل یک بار روی هر یک از ماشین پردازش شود. اما زمان پردازش یک کار روی برخی از ماشینها میتواند صفر باشد. هیچ محدودیتی نیز در مورد توالی پردازش یک کار روی ماشینها وجود ندارد. به عبارت دیگر، تفاوت کارگاه باز با کار کارگاهی در این است که برخلاف کار کارگاهی، مسیر پردازش کارها روی ماشینها ثابت و از پیش تعیین شده نیست و بر اساس ماهیت تابع هدف، مسیر پردازش هر کار روی ماشینها را تعیین کند. در نتیجه مسیر پردازش کارهای مختلف میتواند متفاوت باشد.
محدودیت‌های پردازش و محیط
در محیطهای تولیدی و خدماتی، محدودیتهای متفاوتی ممکن است وجود داشته باشد که حل مسأله زمانبندی نیازمند رعایت این محدودیتها است. تعدادی از این محدودیتها به قرار زیر هستند:
زمانهای آماده‌سازی وابسته به توالی[11] () : در برخی موارد، ماشینها پیش از شروع پردازش یک کار نیازمند آماده‌سازی هستند که این زمان آمادهسازی وابسته به کار اول () و کار دوم () است. در صورتی که زمان آماده‌سازی برای ماشینهای مختلف، متفاوت باشد، زمان آماده‌سازی وابسته به توالی با نماد نمایش داده میشود که به معنی زمان آمادهسازی ماشین ام پیش از پردازش کار و پس از پردازش کار j است.

 

دانلود متن کامل این پایان نامه در سایت abisho.ir