با سلام خدمت کاربران در صورتی که با خطای سیستم پرداخت بانکی مواجه شدید از طریق کارت به کارت مقاله خود را دریافت کنید (تا مشکل رفع گردد). با تشکر از صبوری شما!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
دسته بندی:
رمزنگاری - Cryptography
سال انتشار:
0
ترجمه فارسی عنوان مقاله:
زمانبندی بدون معطلی برای قفل¬ها
عنوان انگلیسی مقاله:
No-wait scheduling for locks
منبع:
نویسنده:
Ward Passchyn, Dirk Briskorn, Frits C.R. Spieksma
چکیده انگلیسی:
We investigate the problem of scheduling a lock with parallel chambers. We show how this problem relates to known interval scheduling problems. We focus on the existence of no-wait schedules, and we consider the complexity of different problem variants. In particular, for a lock consisting of two chambers, we characterize feasibility, and obtain a linear-time algorithm. We also provide an efficient algorithm for the case where all chambers of the lock are identical. Furthermore, we describe a dynamic programming approach for the general case with arbitrary chambers, and prove that the problem is strongly NP-complete when the number of chambers is part of the input.
چکیده فارسی:
ما مسأله¬ی زمانبندی یک قفل دارای جایگاه¬های موازی را مورد بررسی قرار دادیم. ما نشان دادیم این مسأله به چه نحو با مسائل زمانبندی بازه¬ای شناخته¬شده ارتباط پیدا می¬کند. ما بر وجود زمانبندی¬های بدون معطلی تمرکز نموده و پیچیدگی انواع مختلف اینگونه مسائل را در نظر گرفتیم. بطور خاص برای یک قفل متشکل از دو جایگاه، عملی بودن راه¬حل را آزمودیم و به یک الگوریتم زمان خطی دست یافتیم. ما یک الگوریتم کارآمد برای مواردی که در آن تمامی جایگاه¬های قفل، یکسان باشند نیز ارائه نمودیم. به علاوه، ما یک روش برنامه¬ریزی پویا برای یک مورد کلی با جایگاه¬های دلخواه تعریف نموده و اثبات کردیم که این مسأله زمانیکه تعداد جایگاه¬ها جزو ورودی¬ها باشد، یک مسأله¬ی NP-کامل است.
حجم فایل: 426 کیلوبایت
قیمت: ترجمه این مقاله رایگان است
توضیحات اضافی: نظر
تعداد نظرات : 0