بخشی از مقاله
مقدمه1
در تحقیقات مسائل زمانبندی ماشینآلات عموماً فرض میشود که کارها بهصورت متمرکز و در یک کارخانه تولید میگردد. با پیچیدهتر شدن مسائل واقعی و با روند جهانیسازی موجود، حجم بالای تقاضاهای متنوع در بازارها، رقابت شدید و فشار در نوآوری جهت به دست آوردن هر چه بیشتر منافع حاصل از آن موجب شده که رویکرد متمرکز کارایی کافی را در جهان واقعی نداشته باشد. برای حفظ شرایط رقابتپذیری در چنین بازارهایی، کارخانهها با رشد خود
.1 نویسنده مسئول.
تلفن: 0811-8292505، پست الکترونیکی: Behnamian@basu.ac.ir
به طور پیش فرض به پیکربندی داخلی میپردازند تا بواسطه افزایش در سطح ظرفیت از اقتصاد مقیاس برخوردار شوند. با استمرار رشد، کارخانهها تصمیم به ایجاد شبکه تولیدی متشکل از چندین سایت مینمایند. این تغییر و تحول در کارخانه های تولیدی و نیز علاقه شرکتهای کوچکتر برای ورود به عرصه جهانی چالشی جدید در ساختاربندی، مدیریت و عملیات کارا در شبکههای حاصل که به صورت جغرافیایی توزیعشدهاند، بوجود آورده است.
در سال های اخیر نیز در منابع اصلی زمانبندی به اهمیت موضوع این مقاله و کاربردهای واقعی آن در برنامهریزی به وضوح اشاره شده است بهطوریکه در آخرین چاپ کتاب پیندو [1] ، در آخرین بخش کتاب با نام "آنچه پیش روی محققان است" به موضوع زمانبندی چند عاملی اشاره شده است. در این بخش با توضیح در مورد اینکه
ارائه الگوریتم ترکیبی بر پایه بهینه سازی گروه ذرات و روش هایپرهیوریستیک برای زمانبندی کارخانه های توزیع شده با اتحاد مجازی 2
روند توسعه در بازارها سبب حرکت سیستم تولیدی از حالت تک کارخانهای به چندکارخانهای شده است، به محققین و خوانندگان به عنوان زمینههای تحقیقات آتی زمانبندی در این محیطها را پیشنهاد نموده است.
در این راستا در اکثر تحقیقات گذشته در حیطه زمانبندی توزیعشده فرض بر این بوده است که کارخانهها تک ماشین بوده و نیز در حالت چند ماشینی فرض شده است که کارخانهها کاملاً یکسان هستند. ولی در واقعیت همواره این فرض برقرار نبوده و هر کارخانه توانمندیها و محدودیتهای مخصوص به خود را دارد. علاوه بر این در تمام تحقیقات گذشته فرض بر یکسانی اهداف کارخانهها بوده است. به عبارت سادهتر فرض شده است که تمام کارخانههای مورد زمانبندی یک اداره مرکزی واحد و در نتیجه تابع هدف یکسانی دارند. حال شرایطی را در نظر بگیرید که در آن چند شرکت با مالکیت مجزا به این نتیجه برسند که با ایجاد یک شبکه تولید مجازی میتوانند به منافع بیشتری نسب به حالتی که بصورت مجزا فعالیت میکنند دست یابند. در چنین شرایطی هر یک از کارخانهها ممکن است هدف متفاوتی داشته و این هدف در مقایسه با هدف کلی شبکه زمانبندی توزیعشده مجازی در اولویت است. در این حالت زمانبندی توزیعشدهای وجود خواهد داشت که عوامل تابع هدفهای مختلفی دارند. حالت واقعیتری را نیز میتوان در نظر گرفت که در آن کارخانهها توابع هدف چندگانه دارند.
در ادامه بعد از مرور ادبیات در بخش دوم، به دلیل جدید بودن زمانبندی در محیط اتحاد مجازی، در بخش سوم مفهوم اتحاد مجازی تشریح و فرضیات مساله بازگو خواهد شد. در بخش چهارم الگوریتم پیشنهادی ارائه و نتایج عددی آن در بخش پنجم گزارش میگردد. در نهایت نیز در بخش آخر پس از ارائه جمعبندی، زمینههای مطالعات آتی پیشنهاد میگردد.
-2 مرور ادبیات
تولید در محیط توزیعشده در شبکه تولید چندکارخانهای جزء جذابترین موضوعات چند سال اخیر است .[2] زمانبندی کارا برای کارخانهها جهت ماندن در میدان رقابت برای پاسخگویی به تغییرات بازار امری ضروری است و سبب شده است تا این موضوع از ابتدای قرن جاری در دو بخش صنعت و محیط دانشگاهی بطور همزمان مورد توجه قرار گیرد .[3] در این زمینه مقالات متعددی در سالهای اخیر به چاپ رسیده است .[4]
نظر به اینکه زمانبندی توزیعشده با کارخانههای موازی که خود محیط ماشینهای موازی دارند شامل دوتخصیص (تخصیص کار به کارخانه مناسب و تخصیص کارها به هر ماشین در هر کارخانه) است، میتوان نتیجه گرفت که این محیط جزء سختترین مسائل در محیط زمانبندی چند کارخانهای است. به همین دلیل تعداد تحقیقات انجام شده در این زمینه در مقایسه با سایر محیطهای
تولیدی کمتر بوده و محدود به پنج مطالعه در شرایط ساده شده از واقعیت است که در ادامه به مرور آنها خواهیم پرداخت.
سیکریلیو و اسمیت[5] 1 روشی بر پایه رفتار زنبورها با نام عوامل زنبور-مانند2 برای هماهنگی بین کارخانهای توزیعشده با ماشینهای موازی ارائه نمودند. این عوامل مدلی بر اساس رفتار زنبورها در تخصیص کارها دارند که در آن در مورد اینکه آیا کار جدید در صف انتظار پردازش ماشینی پذیرفته گردد یا نه تصمیم گرفته میشود. همچنین در این رویکرد برای کارهای ورودی به سیستم، استراتژی بر پایه مفهوم تئوری مزایده ارائه شده است. آنها با استفاده از مسائل واقعی تخصیص واگنهای به ایستگاههایی که وظیفه رنگ آمیزی آنها را دارند، کارایی عملکرد روش پیشنهادی خود را آزمودند.
در تحقیقی مشابه، هوکو[6] 3 روشی ترکیبی شامل برنامهریزی عدد صحیح4 و برنامهریزی محدودیت ها جهت حل مساله برنامهریزی و زمانبندی در محیط چند کارخانهای با ماشینهای موازی ارائه نمودند. در این مطالعه، محققین با استفاده از مدلبندی ریاضی عدد صحیح مختلط، کارها را به کارخانه مناسب تخصیص داده و با استفاده از روش برنامهریزی محدودیت ها، کارهای تخصیصی به هر کارخانه را زمانبندی نمودند. در اینجا در شرایط برابری زمان ورود کارها به کارگاه5 و سررسید تمام کارها، آنها به دنبال حداقل کردن هزینهها به همراه حداقل کردن زمان انجام کل کارها بودند.
چن و پاندو [7] 6 پیچیدگی زمانبندی در زنجیره تامین در حالات مختلف را بررسی و روش های ابتکاری سریعی برای هر یک از حالات پیشنهاد نمودند. مساله در نظر گرفته شده در این تحقیق شبکه تولید و توزیع شامل چندین کارخانه موازی در کشورهای خارجی و یک مرکز توزیع داخلی7 است. در این شبکه ابتدا کارها در کارخانهها پردازش و سپس به مرکز توزیع حمل میشود تا بین خرده فروشان کشورهای دیگر توزیع گردد. با توجه به تنوع در بهره وری و هزینهها در کارخانههای مختلف، هزینهها و زمانهای پردازش بسته به آنکه کار در کدام کارخانه انجام شود، متفاوت است. نویسندگان در این مقاله برای مساله خود چهار تابع هدف مختلف در نظر گرفته که همگی آنها شامل زمانهای تحویل و هزینههای تولید و توزیع بودند. در این مطالعه برای هر کدام از این حالات پیچیدگی مساله بررسی و روشی ابتکاری برای آن ارائه شده است. کارل و گروسو[8] 8 یک سیستم تخصیص چند کاربری در شرایط خودخواهانه بودن کاربران9 را در قالب یک بازی غیر همکارانه در محیط ماشینهای موازی مدلبندی کردند. به دلیل نبود هماهنگی بین کاربران، در این مدل
1 . Cicirello and Smith 2 . Wasp-like agents 3. Hooker
4. Mixed integer linear programming (MILP) 5 . Release date 6 . Chen and Pundoor 7 . Distributed center 8 . Carroll and Grosu
9 . Selfish multi-user job scheduling
3 نشریه پژوهشهای مهندسی صنایع در سیستمهای تولید / سال اول / شماره اول / بهار و تابستان 1392
هزینه اغتشاش در راستای کمی کردن معیارهای ارزیابی سیستم در نظر گرفته شده و بر اساس آن زمانبندی صورت میگیرد.
به تازگی بهنامیان و فاطمی قمی [9] مساله زمانبندی تولید چندکارخانه ای را در نظر گرفتند. برای حل مساله شبکه تولیدی با چندین کارخانه های توزیعشده که با هدف تامین نیاز بازار آنجا ایجاد شده اند، محققین روش فراابتکاری بر پایه رقابت استعماری ارائه نموده و در نهایت کارایی روش را گزارش کردند.
در تحقیق حاضر با وجود تک هدفه بودن مساله، بحث جوابهای غالب و مغلوب برای اولین بار در فضای مسائل تک هدفی مطرح شده است. همچنین الگوریتم ترکیبی جدیدی برای حل مساله پیشنهاد گردیده است.
-3 تعریف مساله و تحلیل ویژگیهای آن
بازار نقشی کلیدی در تعریف اهداف اصلی در سیستمهای تولیدی دارد. نیاز به نوآوری، تولید بر پایه خواسته مشتری و پاسخ سریع به تقاضاها از ویژگی های چنین بازارهایی است. ویژگی دیگر این بازارها پویایی و تصادفی بودن آنها است. سیستمهای تولید سنتی، به دلایل زیر قادر به پاسخگویی به این بازارها نیستند :[10]
1. زمان پاسخ به برآشفتگیهای تصادفی بزرگ در بازار به دلیل کند بودن سیستمهای تولید سنتی، رضایت بخش نیست.
2. اطلاعات ناکافی، نادرست و غیر قابل اعتماد به دلیل بزرگی جغرافیایی توزیع مشتریان سبب شده است تا تصمیمگیرندگان بر پایه حدس و یا اطلاعات بسیار کم تصمیمگیری کنند.
3. ساختار سازمانی سیستمهای سنتی از پیش تعیین شده و بسیار خشک است و این امر سبب میشود که در برابر پیدایش بازارهای جدید و تغییرات آن منعطف نباشند.
به منظور غلبه بر چنین معایبی، سیستمهای جدید تولیدی حاصل از مشارکت چندین کارخانه به وجود آمدهاند. امروزه کارخانهها علاقمند به ایجاد ارتباطات موازی بوده تا بتوانند از منافع حضور در چنین شبکههایی برای بهبود وضعیت رقابتی خود استفاده کنند. چنین به اشتراکگذاری منابع توزیعشده در نقاط مختلف جغرافیایی باعث پیدایش شبکههای تولیدی میشود که یکی از اقسام آنها شبکه با اعضای خودخواه 1 است که به نوعی تشکیل یک شبکه مجازی2 را میدهد. همچنان که در شکل (1) آمده است این نوع مشارکت جزء مشارکت کوتاه مدت بوده و دوام آن تا زمانی است که اعضا به منافع بیشتری در مقایسه با حالتی که انفرادی فعالیت کنند، دست یابند. در شبکههای مجازی، مهمترین مساله مدیریت منافع محدود با توجه به شرایط اعضا است به گونهای که مجموعه نسبت به شرایط داخلی و بیرونی منعطفتر شود. گاه ممکن است حتی
1. Self-interested 2. Virtual network
شرکتها برای آنکه بتوانند یک سفارش بزرگتر از توان خود را بپذیرند و انجام دهند، در چنین اتحادهای موقتی شرکت و پس از اتمام تولید این سفارش خاص، هر یک از اعضا راه خود را بپیماید .[11]
شکل :(1) دسته بندی انواع شبکه های تولیدی [11]
اعضای این شبکهها با وجود اینکه محصول واحدی را تولید میکنند، اما به دلایل مختلف همچون قدمت ماشین آلات و یا تکنولوژی آنها، سرعت تولید در اعضای مختلف، ممکن است همسان نباشند. در این مقاله فرض شده است چنین کارخانههای ناهمسانی در شبکه وجود داشته که هر یک با همکاری سایر اعضا در وهله اول موظف به ارضاء نیاز بازار خود بوده و نیز میتوانند در این تولید تابع هدفی متفاوت از دیگران داشته باشند. مثال های واقعی مختلفی با چنین شرایطی در جهان واقعی وجود دارد که از آن جمله میتوان به صنایع هوانوردی و صنایع خودرو اشاره کرد.
فرضیات اصلی مساله زمانبندی توزیع شده مـورد بررسـی ایـن رساله به شرح زیر است:
1. مساله F کارخانه ناهمسان موازی با ماشـین هـای مـوازی دارد.
2. کار باید زمانبندی شـوند کـه ازیکـدیگر مسـتقل انـد و نسبت به یکدیگر اولویت خاصی ندارند.
3. تمام کارها و ماشین آلات بطـور همزمـان در ابتـدای دوره برنامهریزی در دسترساند.
4. بریدگی و تقسیم یک کار خاص مجاز نیست.
5. هرگز ماشینآلات خراب نمیشوند.
6. زمان های حمل و نقل درون کارخانه ای ناچیز بوده و یا در زمان انجام کار لحاظ شدهاند.
7. زمانهای آمادهسازی ناچیز و قابل چشمپوشی هستند.
8. هر کار باید دقیقاً به یکی از کارخانههای تولیدی اختصاص یابد.
شکل (2) مقایسه بین فعالیت انفرادی کارخانهها و ایجاد شبکه مجازی در رسیدن به سه عامل مهم توانمندساز کارخانهها (نوآوری، انعطافپذیری و رقابت هزینهای) را نشان میدهد .[12]
ارائه الگوریتم ترکیبی بر پایه بهینه سازی گروه ذرات و روش هایپرهیوریستیک برای زمانبندی کارخانه های توزیع شده با اتحاد مجازی 4
شکل :(2) مقایسه بین کارخانه انفرادی و شبکه مجازی [12]
در این شبکه فرض شده است که دو دسته تابع هدف وجود دارد به گونهای که گروهی از کارخانهها تابع هدف زمان تکمیل کل کارها را در تولید داشته و گروهی دیگر تابع هدف مجموع زمانهای تکمیل را دارند. در این مطالعه علاوه بر در نظر گرفتن دو حالت از این توابع، حالت سومی نیز در مساله زمانبندی شبکه مجازی تولید در نظر گرفته شده که در آن تابع هدف حداقل کردن هزینههای پردازش، زودکرد و دیرکرد است که البته با در نظر گرفتن تفاوت این هزینهها در کارخانههای مختلف، مساله جذابتر شده است. در این حالت نیز پس از حل دقیق مساله در اندازههای کوچک، روش جدیدی در قالب الگوریتم مونتکارلو برای اندازههای بزرگ مساله ارائه شده است.
قبل از طراحی الگوریتمها، میخواهیم با یک مثال ساده برای 2 کارخانه 3 و 2 ماشینی با 12 کار، نشان دهیم در محیط شبکه مجازی تولید توزیعشده چگونه حتی با یک تابع هدف یکسان نیز بحث جوابهای مسلط مطرح است. جدول (1) مشخصههای عددی مساله نمونه مورد بررسی را نشان میدهد.
جدول (1) جدول زمانهای پردازش کارها در کارخانه های 1 و 2
زمانهای کارهای متعلق به R1
پردازش 1 2 3 4 5 6
40 50 10 40 30 50
20 25 5 20 15 25
زمانهای کارهای متعلق به R2
پردازش 7 8 9 10 11 12
50 40 10 30 40 20
25 20 5 15 20 10
در این جدول از نمادهای R1 و R2 استفاده شده است تا نشان داده شود کارخانهها چه تابع هدفی دارند. در این رابطه و نیز به ترتیب نشان دهنده زمانهای پردازش در R1 و R2 هستند.
شکل (3) نتایج حاصل از دو جواب تصادفی در قالب نمودار گانت
