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).