عنوان پایان‌نامه
زمان بندی کارها روی ماشینها بازمان شروع معین
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 75.;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 68326
- تاریخ دفاع
- ۱۲ شهریور ۱۳۹۳
- دانشجو
- ایمان محمدی
- استاد راهنما
- دارا معظمی
- چکیده
- مسئله زمانبندی آنلاین کارهای قابل پس گرفتن با زمان شروع اجرای ثابت روی m ماشین، با هدف ماکسیمم کردن سود حاصل از مجموع کارهای به طور کامل اجرا شده را در نظر میگیریم. در این مسئله کارها در زمان های مختلف منتشر می شوند، هر کار دارای سایز و وزنی مرتبط با آن می باشد. کار جدیدی که منتشر می شود باید بلافاصله به ماشینی منتسب شود و اجرای آن شروع شود، یا در غیره اینصورت کار نادیده گرفته شده و از بین خواهد رفت. همچنین این قابلیت وجود دارد تا کاری که در حال اجرا روی یک ماشین می باشد را در حین اجرا از ماشین پس گرفته تا ماشین بیکار شود و بتوان کار دیگری به آن منتسب کرد، اما این نکته وجود دارد که تنها کارهایی که به صورت کامل اجرا شده اند، در سود حاصل از اجرای الگوریتم نقش خواهند داشت و کارهایی که در حین اجرا پس گرفته شده اند از بین می روند و امکان آن وجود ندارد که در آینده اجرای آن ها ادامه یابد. مطالعات زیادی در مورد این مسئله انجام شده است، که کاربردهای فراوانی نیز دارد، برای مثال مسئله ی برنامه ریزی کاری برای پرسنل و مسئله ی اختصاص پهنای باند به کانال های مخابراتی از جمله ی آن ها می باشد. در حالت کلی نمی توان الگوریتم تقریبی کران داری برای حل این مسئله طراحی کرد، لذا ما تعدادی از کلاس های استاندارد و معروف این مسئله را در نظر گرفته ایم و نشان داده ایم آن لاین الگوریتم های معروفی که برای حل آن ها استفاده شده اند، چگونه کار می کنند. از جمله ی این کلاس ها می توان به مسائلی اشاره کرد که وزن و یا سایز کارها ثابت باشد، یا اینکه وزن کارها تابعی از سایز آن ها باشد. در مورد مسئله ای که ماشین ها همسان باشند و وزن کارها تابعی D-benevolent از سایز آن ها باشد، بهترین الگوریتمی که برای حل آن ها وجود دارد دارای فاکتور 4m می باشد و ما الگوریتمی بهتر ارائه داده ایم که دارای فاکتور 2m+4 است، که این پیشرفت مناسبی است، چرا که معمولا بهبود دادن کران های الگوریتم های تقریبی در اینگونه مسائل در حد چند دهم می باشد. در آخر زمینه های مطالعاتی برای ادامه ی مسیر نشان داده شده است. و اینکه چه فاکتور هایی برای طراحی الگوریتم های بهتر در این زمینه وجود دارد.
- Abstract
- We consider online scheduling of jobs with specific release time on m machines. Each job has a weight and a size; the goal is maximizing total weight of completed jobs. At release time of a job it must immediately be scheduled on a machine or it will be rejected. It also allowed during execution of a job to preempt it, but it will be lost and only weight of completed jobs contribute on profit of algorithm. Scheduling jobs with ?xed start times to maximize (weighted) throughput is a well-studied problem with many applications, for instance work planning for personnel, call control and bandwidth allocation in communication channels. In general case cannot have any algorithm with bounded competitive ratio. Therefore in this thesis we consider a number of standard variants. We give a full classi?cation of the variants into cases which admit constant competitive ratio (weighted and unweighted unit jobs, and C-benevolent instances, which is a wide class of instances containing proportional-weight jobs), and cases which admit only a linear competitive ratio (unweighted jobs and D-benevolent instances). In particular, we give a new algorithm for scheduling D-benevolent instances on m identical machines, which admits 2m+4 competitive ratio. That is a well improve in the problem because previous known result, admits 4m competitive ratio. Finally we give a comparison between our algorithm and previous results and give some point to how our algorithm could be improved in future.
