پرش به محتویات

زمان‌بندی کارها روی یک ماشین

این مسئله در مورد یافتن یک زمان‌بندی بهینه برای $n$ کار روی یک ماشین واحد است، اگر کار $i$ در زمان $t_i$ قابل پردازش باشد، اما به ازای $t$ ثانیه انتظار قبل از پردازش کار، جریمه‌ای معادل $f_i(t)$ باید پرداخت شود.

بنابراین، مسئله به دنبال یافتن جایگشتی از کارها است که جریمه کل را کمینه کند. اگر $\pi$ را جایگشت کارها در نظر بگیریم (که در آن $\pi_1$ اولین کار پردازش شده، $\pi_2$ دومین کار و الی آخر است)، آنگاه جریمه کل برابر است با:

$$F(\pi) = f_{\pi_1}(0) + f_{\pi_2}(t_{\pi_1}) + f_{\pi_3}(t_{\pi_1} + t_{\pi_2}) + \dots + f_{\pi_n}\left(\sum_{i=1}^{n-1} t_{\pi_i}\right)$$

راه حل برای موارد خاص

توابع جریمه خطی

ابتدا مسئله را برای حالتی حل می‌کنیم که تمام توابع جریمه $f_i(t)$ خطی باشند، یعنی به شکل $f_i(t) = c_i \cdot t$ باشند که در آن $c_i$ یک عدد نامنفی است. توجه داشته باشید که این توابع جمله ثابت ندارند. در غیر این صورت، می‌توانیم تمام جملات ثابت را با هم جمع کرده و مسئله را بدون آن‌ها حل کنیم.

یک جایگشت $\pi$ را ثابت در نظر می‌گیریم و اندیس $i = 1 \dots n-1$ را انتخاب می‌کنیم. فرض کنید جایگشت $\pi'$ همان جایگشت $\pi$ است با این تفاوت که عناصر $i$ و $i+1$ جابجا شده‌اند. بیایید ببینیم جریمه چقدر تغییر کرده است.

$$F(\pi') - F(\pi) =$$

به راحتی می‌توان دید که تغییرات فقط در جملات $i$-ام و $(i+1)$-ام رخ می‌دهند:

$$\begin{align} &= c_{\pi_i'} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_{i+1}'} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_{i+1}} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_i} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_i} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \end{align}$$

به راحتی می‌توان دریافت که اگر زمان‌بندی $\pi$ بهینه باشد، هر تغییری در آن منجر به افزایش جریمه (یا جریمه یکسان) می‌شود. بنابراین، برای زمان‌بندی بهینه می‌توانیم شرط زیر را بنویسیم:

$$c_{\pi_{i}} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \ge 0 \quad \forall i = 1 \dots n-1$$

و پس از بازآرایی به دست می‌آوریم:

$$\frac{c_{\pi_i}}{t_{\pi_i}} \ge \frac{c_{\pi_{i+1}}}{t_{\pi_{i+1}}} \quad \forall i = 1 \dots n-1$$

بنابراین، زمان‌بندی بهینه با مرتب‌سازی ساده کارها بر اساس کسر $\frac{c_i}{t_i}$ به ترتیب غیرصعودی به دست می‌آید.

لازم به ذکر است که ما این الگوریتم را با استفاده از روشی به نام روش جایگشتی ساختیم: دو عنصر مجاور را جابجا کردیم، میزان تغییر جریمه را محاسبه کردیم و سپس الگوریتمی برای یافتن روش بهینه استخراج کردیم.

تابع جریمه نمایی

فرض کنید تابع جریمه به شکل زیر باشد:

$$f_i(t) = c_i \cdot e^{\alpha \cdot t},$$

که در آن تمام اعداد $c_i$ نامنفی و ثابت $\alpha$ مثبت است.

با به کار بردن روش جایگشتی، به راحتی می‌توان تشخیص داد که کارها باید بر اساس مقدار زیر به ترتیب غیرصعودی مرتب شوند:

$$v_i = \frac{1 - e^{\alpha \cdot t_i}}{c_i}$$

تابع جریمه یکنواخت یکسان

در این حالت، موردی را در نظر می‌گیریم که تمام توابع $f_i(t)$ با هم برابر بوده و این تابع یکنواخت صعودی باشد.

واضح است که در این حالت، جایگشت بهینه، چیدن کارها بر اساس زمان پردازش $t_i$ به ترتیب غیرنزولی است.

قضیه لیوشیتس-کلادوف

قضیه لیوشیتس-کلادوف بیان می‌کند که روش جایگشتی تنها برای سه حالت ذکر شده در بالا قابل استفاده است، یعنی:

  • حالت خطی: $f_i(t) = c_i \cdot t + d_i$، که در آن $c_i$ ثابت‌های نامنفی هستند،
  • حالت نمایی: $f_i(t) = c_i \cdot e^{\alpha \cdot t} + d_i$، که در آن $c_i$ و $\alpha$ ثابت‌های مثبت هستند،
  • حالت یکسان: $f_i(t) = \phi(t)$، که در آن $\phi$ یک تابع یکنواخت صعودی است.

در تمام موارد دیگر، این روش قابل استفاده نیست.

این قضیه تحت این فرض اثبات شده است که توابع جریمه به اندازه کافی هموار باشند (مشتقات سوم آن‌ها موجود باشد).

در هر سه حالت، ما از روش جایگشتی استفاده می‌کنیم که از طریق آن می‌توان زمان‌بندی بهینه مورد نظر را با مرتب‌سازی پیدا کرد، بنابراین در زمان $O(n \log n)$ قابل حل است.