بخشی از پاورپوینت
اسلاید 1 :
بنام خدا
تئوری توالی عملیات (21516 (
اسلاید 2 :
تئوری توالی عملیات (21516 (
بخش اول:
مدل های قطعی
اسلاید 3 :
تئوری توالی عملیات (21516 (- فصل دوم
فصل دوم
مدل های قطعی: پیش نیازها
مطالعه و تحقیق به روی مدل های قطعی زمان بندی از 4 دهه قبل آغاز شده است.
مدلهای متنوع ومتفاوتی در این زمینه موجود است.
نیاز به ایجاد استانداردی برای طبقه بندی مدل های موجود
اسلاید 4 :
تئوری توالی عملیات (21516 (- فصل دوم
در بخش اول این فصل نحوه استاندارد نمایش این مسایل (نه تمامی آنها) ارایه می شود.
در بخش دوم تعدادی مثال از مسایل مربوطه ارایه شده و تعدادی از نقاط ضعف استاندارد ارایه شده مورد بحث قرار می گیرد.
در بخش سوم کلاس های مختلف زمانبندی بر اساس میزان آزادی برنامه ریز برای تصمیم گیری تعریف می شود.
بخش چهارم به بحث در مورد پیچیدگی مسایل معرفی شده در قسمت اول می پردازد.
اسلاید 5 :
تئوری توالی عملیات (21516 (- فصل دوم
2.1چار چوب ها و نمادها
در تمامی مسایل مورد بررسی زمانبندی تعداد ماشین ها (منابع) و کارها (فعالیت ها) محدود می باشند.
تعداد کارها معمولا با n و تعداد ماشین ها با m نمایش داده می شود.
هنگام اشاره به یک کار از نماد j و هنگام اشاره به یک ماشین از نماد i استفاده می شود.
اسلاید 6 :
تئوری توالی عملیات (21516 (- فصل دوم
چار چوب ها و نمادها (ادامه)
اگر کاری نیاز به پردازش و یا عملیات متعددی به روی ماشین های متفاوتی داشته باشد، آنگاه زوج مرتب (i , j) برای تعریف عملیات مذکور به کار می رود (عملیات مورد نیاز برای کار jام به روی ماشین iام). تعاریف مربوطه عبارتند از:
زمان پردازش هر عملیات :(Pij)زمان انجام عملیات برای کار jام به روی ماشین ماشین iام. در حالتی که زمان پردازش عملیات مستقل از ماشین باشد و یا عملیات فقط به روی یک ماشین انجام شود نماد i حذف می شود.
اسلاید 7 :
تئوری توالی عملیات (21516 (- فصل دوم
چار چوب ها و نمادها (ادامه)
زمان دسترسی به کارRelease date (rj): زمانی است که یک کار وارد کارگاه شده و آماده انجام عملیات به روی ماشین ها است. این زمان زودترین زمانی است که می توان عملیات پردازش را به روی یک کار آغاز نمود.
موعد تحویل Due date (dj): زمانی است که تولید کننده متعهد به تحویل کار به مشتری نهایی است. تحویل کار به مشتری پس از موعد تحویل امکان پذیر است ولی تولید کننده بایستی جریمه ای را بابت دیرکرد بپردازد. در مواردی که محصول بایستی در موعد تحویل تکمیل شود، به آن deadline گویند و زمان آن را بصورت نمایش می دهند.
اسلاید 8 :
تئوری توالی عملیات (21516 (- فصل دوم
وزن(weight) wj : وزن هر کار در واقع بیانگر میزان اهمیت هر کار نسبت به کارهای موجود در سیستم می باشد. به عنوان مثال این وزن می تواند بیانگر هزینه نگهداری هر کار بصورت ناقص در سیستم و یا ارزش کنونی آن باشد.
اسلاید 9 :
تئوری توالی عملیات (21516 (- فصل دوم
یک مساله زمانبندی عمومی می تواند با استفاده از سه نماد بصورت زیر تعریف شود:
α| β| γ
α بیانگر وضعیت و شرایط ماشین یا منبع است و معمولا دارای یک نماد است.
β خصوصیات و جزییات نحوه پردازش و محدودیت های موجود را بیان می کند و ممکن است شامل هیچ نمادی نباشد و یا چندین نماد باشد.
γ بیانگر تابع هدف مساله است و معمولا شامل تنها یک نماد می باشد.
اسلاید 10 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α:
حالت تک ماشین(1):
ساده ترین حالت ممکن است که معمولا حالت خاص سایر مسایل در نظر گرفته می شود.
این حالت Single Machine نام دارد (مثال فروشگاهی با یک باجه فروش).
اسلاید 11 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α:
حالت تک ماشین(1):
اسلاید 12 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α (ادامه) :
ماشین های مشابه بصورت موازی(Pm):
چندین ماشین یکسان بصورت موازی می توانند کار کنند.
فرض می شود که کار j بایستی توسط یکی از این ماشین ها انجام شود.
این حالت با عنوان Identical Machines in Parallel نامیده می شود. (مثال بانک های خصوصی مانند سامان و پارسیان).
اگر یک کار تنها باید به روی یکی از ماشین ها پردازش شود، آنگاه نماد Mj در قسمت β نمایش داده می شود.
مثال هایی دیگر در این زمینه صفوف بازرسی بدنی و یا سیستم های بانک و یا سیستم کنترل گذرنامه در فرودگاه ها می باشند.
اسلاید 13 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α (ادامه) :
ماشین های مشابه بصورت موازی(Pm):
اسلاید 14 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α (ادامه):
ماشین هایی بصورت موازی با سرعت متفاوت (Qm) :
ماشین هایی بصورت موازی با سرعت پردازش متفاوت
سرعت پردازش ماشین iام بصورت vi نمایش داده می شود.
زمان پردازش کار jام به روی ماشین iام بصورت Pij = Pj /vi محاسبه می شود.
چنین مسایلی متعلق به ماشین های مشابه می باشند.
این مسایل با عنوان Machines in Parallel with different speeds تعریف می شوند.
مثالی در این زمینه: تعمیرکاران مختلف ماشین که سرعت آنها بستگی به مهارت آنها دارد (مشتریان ثابت و منابع متحرک).
در این حالت سرعت پردازش هر ماشین مستقل از نوع کار است.
اسلاید 15 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α (ادامه) :
ماشین هایی بصورت موازی با سرعت متفاوت (Qm) :
اسلاید 16 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α (ادامه):
ماشین های متفاوت بصورت موازی (Rm) :
در این حالت ماشین هایی متفاوت بصورت موازی وجود دارند.
ماشین i می تواند کار j را با سرعتی معادل vij پردازش نماید.
زمان پردازش بصورت Pij = Pj /vij محاسبه می شود.
اگرسرعت پردازش کارهامستقل کارها باشد، مساله به حالت قبلی تبدیل می شود.
این حالت با نام Unrelated Machines in Parallel معروف هستند.
در این حالت هر کار ممکن است توسط یکی از ماشین ها با سرعت بالاتری پردازش شود.
اسلاید 17 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α (ادامه) :
ماشین های متفاوت بصورت موازی (Rm) :
اسلاید 18 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α (ادامه):
حالت Flow shop (Fm) :
m ماشین بصورت سری وجود دارند.
هر یک از کارها باید توسط تک تک این ماشین ها با ترتیب مشخص و یکسان برای تمام کارها پردازش گردند.
پس از اینکه یک کار توسط یک ماشین پردازش شد وارد صف ماشین بعدی می شود.
عموما سیاست خدمت دهی در هر صف بصورت FIFO است.
در حالتی که سیاست FIFO در پردازش کارها برقرار باشد مساله با نام permutation flow shop نامیده می شود و در قسمت β کلمه prmu اضافه می گردد.
اسلاید 19 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت های مختلف برای α (ادامه) :
حالت Flow shop (Fm) (ادامه) :
اسلاید 20 :
تئوری توالی عملیات (21516 (- فصل دوم
حالت Flow shop (Fm) (ادامه) :
مثال هایی در این زمینه عبارتند از:
صف غذا در رستوران (غذای اصلی، دسر و. به ترتیب ارایه می شود. سپس مشتریان برای پرداخت به قسمت آخر مراجعه می کند).
صف ورود به استادیوم (خرید بلیت، بازرسی بدنی و ورود به استادیوم)
بازکردن حساب بانکی (ارایه درخواست، بررسی فرم ها، استعلام های مورد نیاز، تایید، چاپ دسته چک و.)
