Đến nội dung


Hình ảnh

Làm thế nào để mọi người ít chờ 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 30-11-2021 - 04:58

Giả sử bạn làm nhân viên quầy thu ngân ở siêu thị. Có $n$ khách hàng đến trước bạn chờ tính tiền. Nhìn vào lượng vật phẩm trong giỏ hàng của họ, bạn nhẩm tính được người $i$ sẽ tốn $p_i$ thời gian để quét xong mã và tính tiền, không kể thời gian đệm giữa hai người khách liên tiếp. Tiếp tục giả sử rằng, bạn có thể tùy ý sắp xếp thứ tự của $n$ khách hàng này. Vậy phương án nào là tối ưu nhất để:

a) Tổng thời gian chờ của mọi người là nhỏ nhất?

b) Tổng thời gian chờ của mọi người là nhỏ nhất, biết rằng một số khách hàng là khách hàng trung thành của cửa hàng, và thời gian chờ của họ sẽ được nhân lên theo hệ số $w_i$ với $w_i$ là trọng số cho biết mức độ quan trọng của khách hàng $i$.

 

===

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:53

Sử dụng ký hiệu Graham, ta nhận dạng bài toán này là:
a) $1 \, | \, | \, \min \sum C_j$ (total completion time)
b) $1 \, | \, | \, \min \sum w_jC_j$ (total weighted completion time)
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 sử dụng để nâng cao năng suất (through-put) của hệ thống, và một cách gián tiếp, giảm thời gian chờ của khách hàng (công việc). Nếu có thêm $r_j$ (release date) thì ta có thể cân nhắc thời gian tồn đọng $F_j$ (flow time) thay cho $C_j$.


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