Đến nội dung


Hình ảnh

Đo lường sự dao động của tài nguyên

scheduling theory

  • Please log in to reply
Chưa có bài trả lời

#1 perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản trị
  • 4537 Bài viết
  • Giới tính:Nam
  • Sở thích:Đàn guitar, ngắm người mình yêu, học toán

Đã gửi 30-08-2022 - 20:38

Trong bài toán RCPSP (Resource Constrained Project Scheduling Problem), tài nguyên (resource) là yếu tố tối quan trọng khi lập lịch cho các công việc, vì công việc không tiến hành nếu không có tài nguyên. Ví dụ, không thể khám bệnh cho bệnh nhân nếu không có bác sĩ đang rảnh tay. Có nhiều cách phân loại các vấn đề RCPSP, nhưng một cách phân loại tiêu biểu là theo sự dao động của tài nguyên:

- Loại 1 là hằng số (constant) : Tài nguyên sẽ luôn hiện hữu với độ lớn (availability) là hằng số. Ví dụ, một ê-kíp trực có 5 y tá từ 21h đến 5h sáng hôm sau. Tại mọi thời điểm sẽ luôn có 5 y tá, dù rảnh hay không.

- Loại 2 là biến thiên (time-varying) : Độ lớn tài nguyên thay đổi theo thời gian. Ví dụ, bác sĩ chỉ làm việc vào buổi sáng thứ hai, tư và sáu. Các thời điểm khác, bác sĩ không có mặt.

 

Ta có thể thấy là sự biến thiên của tài nguyên sẽ ảnh hưởng không ít tới việc lập lịch. Câu hỏi đặt ra là làm sao để đo lường sự biến động này? Để cụ thể hơn, ta lấy một ví dụ như sau.

Trên trục thời gian lập lịch (horizon) $[0;T]$, ta có hàm $R(t)$ biểu diễn độ lớn của tài nguyên tại thời điểm $t$. Dưới đây là minh họa cho 3 trường hợp của $R(t)$.

res_var_illu_crop.png

Tổng lượng tài nguyên $\int_0^T {R\left( t \right)dt}$ trong 3 trường hợp là như nhau, tuy nhiên ta nhận ra về số lượng dao động (số lần lên xuống) thì $R^I > R^{II} > R^{III}$.

Mình có ý tưởng là dựa theo công thức tính độ lệch chuẩn (standard variation):

\[\sqrt {\frac{1}{{N}}\sum\limits_{i = 1}^N {{{\left( {{x_i} - \overline x } \right)}^2}} } \]

Tuy nhiên, công thức này mở rộng thế nào khi có vô hạn $x_i$ ? Hay đúng hơn, nếu ta biết được tập giá trị và tần số của từng giá trị, thì công thức sẽ thay đổi thế nào?

Mình muốn thử như sau nhưng chưa biết đúng hay sai, nên cần mọi người góp ý :D

Trong vấn đề RCPSP, thông thường, phạm vi lập lịch sẽ được chia thành các đoạn $[a_k, b_k[$ rời nhau sao cho $R(t)=c_k \, \forall t \in [a_k, b_k[$.

Ta đề xuất công thức sau:

\[{\sigma _R} = \sqrt {\frac{1}{T}\sum\limits_k^{} {\left( {{b_k} - {a_k}} \right){{\left( {{c_k} - \bar c} \right)}^2}} } \]

Trong đó, $\overline c$ là độ lớn trung bình của tài nguyên: $\overline c  = \frac{1}{T}\int_0^T {R\left( t \right)dt}$

Và để chuẩn hóa về $[0;1]$, ta tính: \[\widetilde {{\sigma _R}} = \frac{{{\sigma _R}}}{{\overline c }}\]


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D

$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$




I'm still there everywhere.





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh