دسته بندی:
رمزنگاری - 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