Đến nội dung

Hình ảnh

Làm thế nào để ít trễ hạn nộp nhất?

- - - - - scheduling theory

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
perfectstrong

perfectstrong

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

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Giả sử bạn có $n$ bài tập cần phải nộp cho giáo viên. Bài tập $i$ có hạn nộp là $d_i$. Sau khi nhìn qua các bài tập, bạn ước lượng được để làm xong bài tập $i$, bạn cần có $p_i$ thời gian. Vậy thì bạn nên làm các bài tập theo thứ tự nào để tối ưu nhất?

a) Thời gian trễ hẹn trễ nhất là nhỏ nhất? (Thời gian trễ hẹn là 0 nếu bài nộp đúng hoặc trước hạn, và bằng hiệu số của thời gian nộp thực sự và hạn nộp)

b) Ít bài trễ hạn nhất?

 

===

Liên quan tới "Bài toán sắp xếp" ở đây: https://diendantoanh...i-toán-sắp-xếp/


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.

#2
perfectstrong

perfectstrong

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

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Sử dụng ký hiệu Graham, ta nhận dạng bài toán này là:

a) $1 \, | \, d_j \, | \, \min T_{\max}$ (maximal tardiness)

b) $1 \, | \, d_j \, | \, \min \sum U_j$ (number of tardy jobs) với $U_j = 1$ nếu $T_j > 0$, còn không $U_j = 0$.

Thông thường, với những hàm mục tiêu kinh điển như trên, ta không cần phải ghi thêm $\min$ hay $\max$.

Hai hàm này thường được dùng để tăng sự hài lòng của khách hàng.

Trong một số trường hợp, hàm $U_j$ có thể nhận giá trị hình phạt (penalty) $\rho_j$ (cố định) hoặc $w_j T_j$ nếu hình phạt tỉ lệ với thời gian trễ nải.


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.





Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: scheduling theory

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

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