دسته بندی:

رمزنگاری - 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 کیلوبایت

---

قیمت:    ترجمه این مقاله رایگان است

---

توضیحات اضافی: نظر

---

---

---