پاورپوینت در مورد زمان بندی (pptx) 55 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 55 اسلاید

قسمتی از متن PowerPoint (.pptx) :

اهداف درس این جلسه حل مساله بهینه‌سازی زمان‌بندی با رویکرد حریصانه مساله کمینه‌سازی زمان کل مساله زمان‌بندی مهلت معین ج) زمان‌بندی (Scheduling) درنظر بگیرید که در یک آرایشگاه تعدادی مشتری در انتظار دریافت خدمات مختلفی مانند اصلاح ساده، اصلاح با شستشو، رنگ مو و ... باشند. هر خدمتی در آرایشگاه زمان یکسانی با بقیه خدمات ندارد و آرایشگر می‌داند که هر خدمتی چه مقدار به طول خواهد انجامید. در این جا هدف آن است تا مشتریان به ترتیبی سرویس بگیرند که مجموع کل زمان‌های صرف شده برای انتظار و سرویس گرفتن کمینه گردد. زمان‌بندی که هدف بالا را تامین کند، زمان‌بندی بهینه نامیده می‌شود. 3 ج) زمان‌بندی اگر زمان سپری شده برای انتظار و سرویس‌گرفتن هر مشتری را زمان سیستم (time in the system) بنامیم ... مساله در اینجا کمینه کردن تمامی زمان‌های سیستم (total time in the system) می‌باشد. این مساله کاربردهای گسترده‌ای مانند ... زمان‌بندی دسترسی کاربران به دیسک به‌گونه‌ایکه کل زمان سپری شده برای انتظار و سرویس‌گرفتن کمینه گردد. 4 ج) زمان‌بندی نوع دیگری از مساله زمان‌بندی وجود دارد که در آن ... هر کار (سرویس/مشتری) زمان یکسانی را برای انجام شدن نیاز دارند ولی ... هر کار مهلت (deadline) ای برای شروع شدن دارد که ... درصورتیکه شروع شود، منفعت (profit) مرتبط با آن حاصل می‌شود. در این مساله زمان‌بندی هدف آن است تا ... کارها به گونه‌ای زمان‌بندی شوند که بیشترین منفعت (total profit) بدست آید. بنابراین در ادامه ابتدا مساله زمان‌بندی بدون مهلت و سپس زمان‌بندی با مهلت ارائه خواهد گردید. 5 ج) زمان‌بندی-کمینه‌سازی زمان کل فرض کنید سه کار و زمان پاسخ‌دهی به آنها به صورت زیر وجود دارد: اگر این سه کار به ترتیب 1،2و 3 زمان‌بندی شوند، زمان سیستم هر کدام به صورت زیر می‌باشد: بنابراین تمامی زمان‌های سیستم به صورت زیر می‌باشد: 6 ج) زمان‌بندی-کمینه‌سازی زمان کل چنانچه تمامی زمان‌بندی‌های ممکن برای سه کار را ایجاد کنیم و برای هر ترتیب تمامی زمان‌های سیستم را محاسبه کنیم، جدول زیر به دست خواهد آمد: که زمان‌بندی [3, 1, 2] با تمامی زمان سیستم 32 بهینه خواهد بود. 7 ج) زمان‌بندی-کمینه‌سازی زمان کل واضح است الگوریتمی که به صورت brute force تمامی زمان‌بندی‌های ممکن را درنظر بگیرد دارای پیچیدگی محاسباتی ... فاکتوریل خواهد بود. همانگونه که مشخص است در مثال قبلی زمان‌بندی بهینه زمان حاصل شد که ... کار با کمترین زمان سرویس ابتدا انجام شد و پس از آن .... کار با زمان سرویس کمتر و ... چنین به نظر می‌رسد که چنین زمان‌بندی‌ای بهینه خواهد بود. 8 ج) زمان‌بندی-کمینه‌سازی زمان کل ابتدا کارها را به ترتیب صعودی مرتب می‌کنیم و while ( the instance is not solved) { schedule the next job;// selection procedure and // feasibility check if ( there are no more jobs) // solution check the instance is solved; } 9