Đế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 trị
  • 4425 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 27-11-2021 - 23:16

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 trị
  • 4425 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 18-12-2021 - 16:47

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.





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

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