Đến nội dung

Hình ảnh

Làm thế nào để mọi người ít chờ nhất?

- - - - - scheduling theory

Lời giải perfectstrong, 09-02-2022 - 03:57

Đây là một bài toán sắp xếp, trong đó ta cần phải xác định cho khách hàng $i$ thời gian bắt đầu $S_i$.

Một lịch trình (schedule) của bài toán là một bộ số $\mathcal{S} = (S_1, S_2, \ldots, S_n) \in \mathbb{R}^{n}$ sao cho $S_i \ge 0$ (chỉ tính từ lúc bắt đầu sắp xếp).

Một nghiệm khả thi (feasible solution) của bài toán sẽ là một lịch trình $\mathcal{S}$ sao cho nếu $i$ đi trước $j$ (ký hiệu $i \prec j$) thì $S_i + p_i \le S_j$ (bởi vì chỉ có một quầy tính tiền, và ta phải xong việc cho người $i$ thì mới bắt đầu công việc của $j$).

Ta ký hiệu thời gian kết thúc công việc của khách $i$ là $C_i$ và ta biết là không thể dừng giữa chừng (non-preemptive) công việc một khi đã bắt đầu  nên $C_i = S_i + p_i$.

Hàm mục tiêu (objective function) đầu tiên của chúng ta là $f(\mathcal{S}) = \sum\limits_{i=1}^{n}C_i$. Tại sao ta chọn hàm này? Ấy là bởi khách hàng $i$ phải chờ từ lúc mốc thời gian bắt đầu (thời điểm $t=0$) tới lúc hoàn tất công việc của $i$ (tức $C_i$), nên khi nói tới thời gian chờ, ta nói tới $C_i$.

Với hai lịch trình $\mathcal{S}_1, \mathcal{S}_2$ khả thi, $\mathcal{S}_1$ được coi là tốt hơn (dominating) $\mathcal{S}_2$ nếu và chỉ nếu $f(\mathcal{S}_1) < f(\mathcal{S}_2)$ (ở đây ta đang tìm cách tối thiểu hóa $f$; trường hợp cực đại hóa $f$ thì sẽ ngược lại).

Để tối thiểu $f$, ta cần tìm nghiệm tối ưu (optimal solution/optimality) $\mathcal{S}^*$ sao cho $\mathcal{S}^*$ là một nghiệm khả thi và $f(\mathcal{S}^*)$ nhỏ nhất (không có lịch trình nào khác tốt hơn).

 

Bây giờ ta có các nhận xét sau đối với $\mathcal{S}^*$:

Nhận xét 1: Nếu khách $i$ được xếp liền trước khách $j$ (tức $i \prec \prec j$) thì không có thời gian trống (idle time) giữa công việc $i$ và $j$, tức là $i \prec \prec j \Rightarrow C_i = S_j$.

Thật vậy, giả sử ngược lại, ta có hai khách $i_0, j_0$ sao cho $i_0$ liền trước $j_0$ mà $C_{i_0} < S_{j_0}$. Ta chứng minh là nghiệm này không tối ưu bằng cách xây dựng một lịch trình khách tốt hơn.

Xét lịch trình $\mathcal{S}' = (S'_1, S'_2, \ldots, S'_n)$ sao cho $S'_k = S_k \, \forall k \ne j_0$ và $S'_{j_0} = C_{i_0}$. Nói nôm na, ta loại trừ khoảng thời gian trống đi và thực hiện công việc của $j_0$ ngay sau khi xong $i_0$.

Dễ thấy $\mathcal{S}'$ cũng khả thi. Mặt khác, điểm kết thúc mới của $j_0$ sẽ sớm hơn, vì $C'_{j_0} = S'_{j_0} + p_{j_0} = C_{i_0} + p_{j_0} < S_{j_0} + p_{j_0} = C_{j_0}$. Do đó $f(\mathcal{S}') < f(\mathcal{S}^*)$: trái với giả thiết tối ưu của $\mathcal{S}^*$.

Hệ quả 1: Với mọi khách hàng $i$, thời gian chờ của $i$ sẽ bằng thời gian thực hiện công việc của $i$ cộng với tổng thời gian thực hiện các công việc xếp trước $i$.

\[{C_i} = {p_i} + \sum\limits_{j \prec i}^{} {{p_j}} \]

Nhận xét 2: Nếu khách $i$ liền trước khách $j$, thì công việc của $i$ sẽ không lớn hơn của $j$: $i \prec \prec j \Rightarrow p_i \le p_j$.

Tương tự bằng phản chứng, ta sẽ giả sử điều ngược lại rồi xây dựng một lịch trình tốt hơn.

Giả sử tồn tại $i_0, j_0$ sao cho $i_0 \prec \prec j_0$ mà $p_{i_0} > p_{j_0}$.

Xét lịch trình $\mathcal{S}' = (S'_1, S'_2, \ldots, S'_n)$ sao cho $S'_k = S_k \, \forall k \ne i_0, j_0$, và $S'_{j_0} = S_{i_0};S'_{i_0} = C_{j_0}'$.

Nói cách khách, ta đổi vị trí thực hiện công việc của $i_0$ và $j_0$.

Giờ ta chứng minh $f(\mathcal{S}') < f(\mathcal{S})$.

Để thuận tiện tính toán, ta chia tập hợp khách hàng ban đầu, trừ $i_0, j_0$ thành tập $K_{prec} = \{ i \in [1;n] | i \prec i_0\}$ (những người xếp trước $i_0$) và $K_{succ} = \{ i \in [1;n] | j_0 \prec i\}$ (những người xếp sau $j_0$).

Đầu tiên, ta thấy rằng $\mathcal{S}'$ vẫn khả thi và thỏa mãn nhận xét 1. Bạn đọc có thể chứng minh được không? :)

Kế đến, ta có:

- Tổng thời gian chờ của các khách trong $K_{prec}$ và $K_{succ}$ không đổi:

\[\begin{array}{l}
\sum\limits_{i \in {K_{prec}}}^{} {{C_i}'}  = \sum\limits_{i \in {K_{prec}}}^{} {\left( {{S_i}' + {p_i}} \right)}  = \sum\limits_{i \in {K_{prec}}}^{} {\left( {{S_i} + {p_i}} \right)}  = \sum\limits_{i \in {K_{prec}}}^{} {{C_i}} \\
\sum\limits_{i \in {K_{succ}}}^{} {{C_i}'}  = \sum\limits_{i \in {K_{succ}}}^{} {\left( {{S_i}' + {p_i}} \right)}  = \sum\limits_{i \in {K_{succ}}}^{} {\left( {{S_i} + {p_i}} \right)}  = \sum\limits_{i \in {K_{succ}}}^{} {{C_i}}
\end{array}\]

- Tổng thời gian chờ của khách $i_0$ và $j_0$ lại thay đổi (chú ý rằng do nhận xét 1 nên $C_{j_0} = S_{j_0} + p_{j_0} = C_{i_0} + p_{j_0} = S_{i_0} + p_{i_0} + p_{j_0}$)

\[\begin{align*}
{C_{{i_0}}}' + {C_{{j_0}}}' &= {S_{{i_0}}}' + {p_{{i_0}}} + {S_{{j_0}}}' + {p_{{j_0}}}\\
 &= {C_{{j_0}}}' + {p_{{i_0}}} + {S_{{i_0}}} + {p_{{j_0}}}\\
 &= {S_{{j_0}}}' + {p_{{j_0}}} + {p_{{i_0}}} + {S_{{i_0}}} + {p_{{j_0}}}\\
 &= {S_{{i_0}}} + {p_{{j_0}}} + {p_{{i_0}}} + {S_{{i_0}}} + {p_{{j_0}}}\\
 &< \left( {{S_{{i_0}}} + {p_{{j_0}}} + {p_{{i_0}}}} \right) + \left( {{S_{{i_0}}} + {p_{{i_0}}}} \right) = {C_{{j_0}}} + {C_{{i_0}}}
\end{align*}\]

Vậy $f\left( {\mathcal S'} \right) = \sum\limits_{i \in {K_{prec}}}^{} {{C_i}'}  + {C_{{i_0}}}' + {C_{{j_0}}}' + \sum\limits_{i \in {K_{succ}}}^{} {{C_i}'}  < \sum\limits_{i \in {K_{prec}}}^{} {{C_i}}  + {C_{{i_0}}} + {C_{{j_0}}} + \sum\limits_{i \in {K_{succ}}}^{} {{C_i}}  = f\left( \mathcal S^* \right)$: mâu thuẫn với tính tối ưu của $\mathcal S^*$. Nhận xét 2 được chứng minh.

 

Từ nhận xét 2, ta suy ra rằng, công việc nào ít tốn thời gian hơn thì nên xếp trước để mọi người ít chờ hơn. Đây chính là thuật toán SPT (Shortest Processing Time).

Một cách chứng minh khác là dựa trên hệ quả 1 và sử dụng bất đẳng thức hoán vị.

 

Bằng phương pháp tương tự, mời mọi người thử sức với câu b: trường hợp mỗi người có một trọng số tương ứng. Thuật toán trong trường hợp này sẽ là WSPT (Weighted Shortest Processing Time).

Đi đến bài viết »


  • Please log in to reply
Chủ đề này có 2 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 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 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 \, | \, | \, \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.

#3
perfectstrong

perfectstrong

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

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

Đây là một bài toán sắp xếp, trong đó ta cần phải xác định cho khách hàng $i$ thời gian bắt đầu $S_i$.

Một lịch trình (schedule) của bài toán là một bộ số $\mathcal{S} = (S_1, S_2, \ldots, S_n) \in \mathbb{R}^{n}$ sao cho $S_i \ge 0$ (chỉ tính từ lúc bắt đầu sắp xếp).

Một nghiệm khả thi (feasible solution) của bài toán sẽ là một lịch trình $\mathcal{S}$ sao cho nếu $i$ đi trước $j$ (ký hiệu $i \prec j$) thì $S_i + p_i \le S_j$ (bởi vì chỉ có một quầy tính tiền, và ta phải xong việc cho người $i$ thì mới bắt đầu công việc của $j$).

Ta ký hiệu thời gian kết thúc công việc của khách $i$ là $C_i$ và ta biết là không thể dừng giữa chừng (non-preemptive) công việc một khi đã bắt đầu  nên $C_i = S_i + p_i$.

Hàm mục tiêu (objective function) đầu tiên của chúng ta là $f(\mathcal{S}) = \sum\limits_{i=1}^{n}C_i$. Tại sao ta chọn hàm này? Ấy là bởi khách hàng $i$ phải chờ từ lúc mốc thời gian bắt đầu (thời điểm $t=0$) tới lúc hoàn tất công việc của $i$ (tức $C_i$), nên khi nói tới thời gian chờ, ta nói tới $C_i$.

Với hai lịch trình $\mathcal{S}_1, \mathcal{S}_2$ khả thi, $\mathcal{S}_1$ được coi là tốt hơn (dominating) $\mathcal{S}_2$ nếu và chỉ nếu $f(\mathcal{S}_1) < f(\mathcal{S}_2)$ (ở đây ta đang tìm cách tối thiểu hóa $f$; trường hợp cực đại hóa $f$ thì sẽ ngược lại).

Để tối thiểu $f$, ta cần tìm nghiệm tối ưu (optimal solution/optimality) $\mathcal{S}^*$ sao cho $\mathcal{S}^*$ là một nghiệm khả thi và $f(\mathcal{S}^*)$ nhỏ nhất (không có lịch trình nào khác tốt hơn).

 

Bây giờ ta có các nhận xét sau đối với $\mathcal{S}^*$:

Nhận xét 1: Nếu khách $i$ được xếp liền trước khách $j$ (tức $i \prec \prec j$) thì không có thời gian trống (idle time) giữa công việc $i$ và $j$, tức là $i \prec \prec j \Rightarrow C_i = S_j$.

Thật vậy, giả sử ngược lại, ta có hai khách $i_0, j_0$ sao cho $i_0$ liền trước $j_0$ mà $C_{i_0} < S_{j_0}$. Ta chứng minh là nghiệm này không tối ưu bằng cách xây dựng một lịch trình khách tốt hơn.

Xét lịch trình $\mathcal{S}' = (S'_1, S'_2, \ldots, S'_n)$ sao cho $S'_k = S_k \, \forall k \ne j_0$ và $S'_{j_0} = C_{i_0}$. Nói nôm na, ta loại trừ khoảng thời gian trống đi và thực hiện công việc của $j_0$ ngay sau khi xong $i_0$.

Dễ thấy $\mathcal{S}'$ cũng khả thi. Mặt khác, điểm kết thúc mới của $j_0$ sẽ sớm hơn, vì $C'_{j_0} = S'_{j_0} + p_{j_0} = C_{i_0} + p_{j_0} < S_{j_0} + p_{j_0} = C_{j_0}$. Do đó $f(\mathcal{S}') < f(\mathcal{S}^*)$: trái với giả thiết tối ưu của $\mathcal{S}^*$.

Hệ quả 1: Với mọi khách hàng $i$, thời gian chờ của $i$ sẽ bằng thời gian thực hiện công việc của $i$ cộng với tổng thời gian thực hiện các công việc xếp trước $i$.

\[{C_i} = {p_i} + \sum\limits_{j \prec i}^{} {{p_j}} \]

Nhận xét 2: Nếu khách $i$ liền trước khách $j$, thì công việc của $i$ sẽ không lớn hơn của $j$: $i \prec \prec j \Rightarrow p_i \le p_j$.

Tương tự bằng phản chứng, ta sẽ giả sử điều ngược lại rồi xây dựng một lịch trình tốt hơn.

Giả sử tồn tại $i_0, j_0$ sao cho $i_0 \prec \prec j_0$ mà $p_{i_0} > p_{j_0}$.

Xét lịch trình $\mathcal{S}' = (S'_1, S'_2, \ldots, S'_n)$ sao cho $S'_k = S_k \, \forall k \ne i_0, j_0$, và $S'_{j_0} = S_{i_0};S'_{i_0} = C_{j_0}'$.

Nói cách khách, ta đổi vị trí thực hiện công việc của $i_0$ và $j_0$.

Giờ ta chứng minh $f(\mathcal{S}') < f(\mathcal{S})$.

Để thuận tiện tính toán, ta chia tập hợp khách hàng ban đầu, trừ $i_0, j_0$ thành tập $K_{prec} = \{ i \in [1;n] | i \prec i_0\}$ (những người xếp trước $i_0$) và $K_{succ} = \{ i \in [1;n] | j_0 \prec i\}$ (những người xếp sau $j_0$).

Đầu tiên, ta thấy rằng $\mathcal{S}'$ vẫn khả thi và thỏa mãn nhận xét 1. Bạn đọc có thể chứng minh được không? :)

Kế đến, ta có:

- Tổng thời gian chờ của các khách trong $K_{prec}$ và $K_{succ}$ không đổi:

\[\begin{array}{l}
\sum\limits_{i \in {K_{prec}}}^{} {{C_i}'}  = \sum\limits_{i \in {K_{prec}}}^{} {\left( {{S_i}' + {p_i}} \right)}  = \sum\limits_{i \in {K_{prec}}}^{} {\left( {{S_i} + {p_i}} \right)}  = \sum\limits_{i \in {K_{prec}}}^{} {{C_i}} \\
\sum\limits_{i \in {K_{succ}}}^{} {{C_i}'}  = \sum\limits_{i \in {K_{succ}}}^{} {\left( {{S_i}' + {p_i}} \right)}  = \sum\limits_{i \in {K_{succ}}}^{} {\left( {{S_i} + {p_i}} \right)}  = \sum\limits_{i \in {K_{succ}}}^{} {{C_i}}
\end{array}\]

- Tổng thời gian chờ của khách $i_0$ và $j_0$ lại thay đổi (chú ý rằng do nhận xét 1 nên $C_{j_0} = S_{j_0} + p_{j_0} = C_{i_0} + p_{j_0} = S_{i_0} + p_{i_0} + p_{j_0}$)

\[\begin{align*}
{C_{{i_0}}}' + {C_{{j_0}}}' &= {S_{{i_0}}}' + {p_{{i_0}}} + {S_{{j_0}}}' + {p_{{j_0}}}\\
 &= {C_{{j_0}}}' + {p_{{i_0}}} + {S_{{i_0}}} + {p_{{j_0}}}\\
 &= {S_{{j_0}}}' + {p_{{j_0}}} + {p_{{i_0}}} + {S_{{i_0}}} + {p_{{j_0}}}\\
 &= {S_{{i_0}}} + {p_{{j_0}}} + {p_{{i_0}}} + {S_{{i_0}}} + {p_{{j_0}}}\\
 &< \left( {{S_{{i_0}}} + {p_{{j_0}}} + {p_{{i_0}}}} \right) + \left( {{S_{{i_0}}} + {p_{{i_0}}}} \right) = {C_{{j_0}}} + {C_{{i_0}}}
\end{align*}\]

Vậy $f\left( {\mathcal S'} \right) = \sum\limits_{i \in {K_{prec}}}^{} {{C_i}'}  + {C_{{i_0}}}' + {C_{{j_0}}}' + \sum\limits_{i \in {K_{succ}}}^{} {{C_i}'}  < \sum\limits_{i \in {K_{prec}}}^{} {{C_i}}  + {C_{{i_0}}} + {C_{{j_0}}} + \sum\limits_{i \in {K_{succ}}}^{} {{C_i}}  = f\left( \mathcal S^* \right)$: mâu thuẫn với tính tối ưu của $\mathcal S^*$. Nhận xét 2 được chứng minh.

 

Từ nhận xét 2, ta suy ra rằng, công việc nào ít tốn thời gian hơn thì nên xếp trước để mọi người ít chờ hơn. Đây chính là thuật toán SPT (Shortest Processing Time).

Một cách chứng minh khác là dựa trên hệ quả 1 và sử dụng bất đẳng thức hoán vị.

 

Bằng phương pháp tương tự, mời mọi người thử sức với câu b: trường hợp mỗi người có một trọng số tương ứng. Thuật toán trong trường hợp này sẽ là WSPT (Weighted Shortest Processing Time).


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

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

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