1. Mô hình bài toán gốc#
1.1. Biến quyết định#
Gọi E , P , R E, P, R E , P , R
Biến xếp ca thi. Với mỗi môn thi e ∈ E e \in E e ∈ E p ∈ P p \in P p ∈ P
x ( e , p ) = { 1 n e ˆ ˊ u m o ˆ n thi e được x e ˆ ˊ p v a ˋ o ca thi p 0 ngược lại x(e, p) = \begin{cases}
1 & \text{nếu môn thi } e \text{ được xếp vào ca thi } p \\
0 & \text{ngược lại}
\end{cases}
x ( e , p ) = { 1 0 n e ˆ ˊ u m o ˆ n thi e đư ợc x e ˆ ˊ p v a ˋ o ca thi p ng ư ợc lại Biến xếp phòng thi. Với mỗi môn thi e ∈ E e \in E e ∈ E r ∈ R r \in R r ∈ R
y ( e , r ) = { 1 n e ˆ ˊ u m o ˆ n thi e được x e ˆ ˊ p v a ˋ o ph o ˋ ng thi r 0 ngược lại y(e, r) = \begin{cases}
1 & \text{nếu môn thi } e \text{ được xếp vào phòng thi } r \\
0 & \text{ngược lại}
\end{cases}
y ( e , r ) = { 1 0 n e ˆ ˊ u m o ˆ n thi e đư ợc x e ˆ ˊ p v a ˋ o ph o ˋ ng thi r ng ư ợc lại Biến liên kết ca thi - phòng thi. Với mỗi e ∈ E e \in E e ∈ E p ∈ P p \in P p ∈ P r ∈ R r \in R r ∈ R
z ( e , p , r ) = { 1 n e ˆ ˊ u m o ˆ n thi e được x e ˆ ˊ p v a ˋ o ca thi p v a ˋ ph o ˋ ng thi r 0 ngược lại z(e, p, r) = \begin{cases}
1 & \text{nếu môn thi } e \text{ được xếp vào ca thi } p \text{ và phòng thi } r \\
0 & \text{ngược lại}
\end{cases}
z ( e , p , r ) = { 1 0 n e ˆ ˊ u m o ˆ n thi e đư ợc x e ˆ ˊ p v a ˋ o ca thi p v a ˋ ph o ˋ ng thi r ng ư ợc lại Biến z z z x , y x, y x , y z ( e , p , r ) = x ( e , p ) ⋅ y ( e , r ) z(e, p, r) = x(e, p) \cdot y(e, r) z ( e , p , r ) = x ( e , p ) ⋅ y ( e , r )
{ z ( e , p , r ) ≤ x ( e , p ) + y ( e , r ) x ( e , p ) ≤ z ( e , p , r ) y ( e , r ) ≤ z ( e , p , r ) ∀ e ∈ E , p ∈ P , r ∈ R \begin{cases}
z(e, p, r) \leq x(e, p) + y(e, r) \\
x(e, p) \leq z(e, p, r) \\
y(e, r) \leq z(e, p, r)
\end{cases}
\quad \forall e \in E, p \in P, r \in R
⎩ ⎨ ⎧ z ( e , p , r ) ≤ x ( e , p ) + y ( e , r ) x ( e , p ) ≤ z ( e , p , r ) y ( e , r ) ≤ z ( e , p , r ) ∀ e ∈ E , p ∈ P , r ∈ R 1.2. Các ràng buộc#
Mỗi môn thi xếp vào đúng một ca thi
∑ p ∈ P x ( e , p ) = 1 , ∀ e ∈ E \sum \limits_{p \in P} x(e, p) = 1, \quad \forall e \in E
p ∈ P ∑ x ( e , p ) = 1 , ∀ e ∈ E
Tại một ca thi, mỗi sinh viên thi tối đa một môn (S S S E s E_s E s s s s
∑ e ∈ E s x ( e , p ) ≤ 1 , ∀ s ∈ S , p ∈ P \sum \limits_{e \in E_s} x(e, p) \leq 1, \quad \forall s \in S, p \in P
e ∈ E s ∑ x ( e , p ) ≤ 1 , ∀ s ∈ S , p ∈ P
Môn thi không xếp vào ca thi không phù hợp (P e P_e P e e e e
x ( e , p ) = 0 , ∀ e ∈ E , p ∈ P e x(e, p) = 0, \quad \forall e \in E, p \in P_e
x ( e , p ) = 0 , ∀ e ∈ E , p ∈ P e
Thời gian ôn tập tối thiểu (k e k_e k e e e e f ( k ) f(k) f ( k ) k k k P ( p , f ( k e ) ) P(p, f(k_e)) P ( p , f ( k e )) p p p f ( k e ) f(k_e) f ( k e )
x ( e , p ) + ∑ q ∈ P ( p , f ( k e ) ) x ( e ′ , q ) ≤ 1 , ∀ s ∈ S , e ≠ e ′ ∈ E s , p ∈ P x(e, p) + \sum \limits_{q \in P(p, f(k_e))} x(e', q) \leq 1, \quad \forall s \in S, e \neq e' \in E_s, p \in P
x ( e , p ) + q ∈ P ( p , f ( k e )) ∑ x ( e ′ , q ) ≤ 1 , ∀ s ∈ S , e = e ′ ∈ E s , p ∈ P
Môn thi không xếp vào phòng không phù hợp (R e R_e R e e e e
y ( e , r ) = 0 , ∀ e ∈ E , r ∈ R e y(e, r) = 0, \quad \forall e \in E, r \in R_e
y ( e , r ) = 0 , ∀ e ∈ E , r ∈ R e
Đủ chỗ cho môn thi (c r c_r c r r r r q e q_e q e e e e
∑ r ∈ R c r ⋅ y ( e , r ) ≤ q e , ∀ e ∈ E \sum \limits_{r \in R} c_r \cdot y(e, r) \leq q_e, \quad \forall e \in E
r ∈ R ∑ c r ⋅ y ( e , r ) ≤ q e , ∀ e ∈ E
Một phòng chỉ phân cho tối đa một môn tại một ca thi
∑ e ∈ E z ( e , p , r ) ≤ 1 , ∀ r ∈ R , p ∈ P \sum \limits_{e \in E} z(e, p, r) \leq 1, \quad \forall r \in R, p \in P
e ∈ E ∑ z ( e , p , r ) ≤ 1 , ∀ r ∈ R , p ∈ P 1.3. Hàm mục tiêu#
Gọi g ( e ) g(e) g ( e ) e e e t ( e ′ , e , n ) t(e', e, n) t ( e ′ , e , n )
t ( e ′ , e , n ) = { 1 n e ˆ ˊ u m o ˆ n thi e ′ x e ˆ ˊ p trước m o ˆ n thi e đ u ˊ ng n ca 0 ngược lại t(e', e, n) = \begin{cases}
1 & \text{nếu môn thi } e' \text{ xếp trước môn thi } e \text{ đúng } n \text{ ca} \\
0 & \text{ngược lại}
\end{cases}
t ( e ′ , e , n ) = { 1 0 n e ˆ ˊ u m o ˆ n thi e ′ x e ˆ ˊ p tr ư ớc m o ˆ n thi e đ u ˊ ng n ca ng ư ợc lại tuyến tính hóa mối quan hệ của biến này với các biến quyết định như sau
x ( e ′ , p ) + x ( e , p + n ) ≤ 1 + t ( e ′ , e , n ) , ∀ p ∈ P , p + n ∈ P x(e', p) + x(e, p + n) \leq 1 + t(e', e, n), \quad \forall p \in P, p + n \in P
x ( e ′ , p ) + x ( e , p + n ) ≤ 1 + t ( e ′ , e , n ) , ∀ p ∈ P , p + n ∈ P (với mọi s ∈ S s \in S s ∈ S e ≠ e ′ ∈ E s e \neq e' \in E_s e = e ′ ∈ E s f ( k e ) ≤ n < g ( e ) f(k_e) \leq n < g(e) f ( k e ) ≤ n < g ( e )
Thành phần 1 - hạn chế thời gian ôn tập ngắn. Với hằng số γ > 1 \gamma > 1 γ > 1 e ′ e' e ′ e e e n < g ( e ) n < g(e) n < g ( e ) γ g ( e ) − n \gamma^{g(e) - n} γ g ( e ) − n
minimize ∑ s ∈ S ∑ e ≠ e ′ e , e ′ ∈ E s ∑ n = f ( k e ) g ( e ) − 1 γ g ( e ) − n ⋅ t ( e ′ , e , n ) \text{minimize} \quad \sum \limits_{s \in S} \sum \limits_{\substack{e \neq e' \\ e, e' \in E_s}} \sum \limits_{n = f(k_e)}^{g(e) - 1} \gamma^{g(e) - n} \cdot t(e', e, n)
minimize s ∈ S ∑ e = e ′ e , e ′ ∈ E s ∑ n = f ( k e ) ∑ g ( e ) − 1 γ g ( e ) − n ⋅ t ( e ′ , e , n ) Thành phần 2 - hạn chế môn nhiều tín chỉ vào ca cuối ngày. Với P l P_l P l k e ≥ σ k_e \geq \sigma k e ≥ σ
minimize ∑ p ∈ P l ∑ e ∈ E k e ≥ σ k e ⋅ q e ⋅ x ( e , p ) \text{minimize} \quad \sum \limits_{p \in P_l} \sum \limits_{\substack{e \in E \\ k_e \geq \sigma}} k_e \cdot q_e \cdot x(e, p)
minimize p ∈ P l ∑ e ∈ E k e ≥ σ ∑ k e ⋅ q e ⋅ x ( e , p ) Hàm mục tiêu tổng hợp. Kết hợp 2 thành phần trên với trọng số α , β ≥ 0 \alpha, \beta \geq 0 α , β ≥ 0
minimize α ∑ s ∈ S ∑ e ≠ e ′ e , e ′ ∈ E s ∑ n = f ( k e ) g ( e ) − 1 γ g ( e ) − n ⋅ t ( e ′ , e , n ) + β ∑ p ∈ P l ∑ e ∈ E k e ≥ σ k e ⋅ q e ⋅ x ( e , p ) \text{minimize} \quad \alpha \sum \limits_{s \in S} \sum \limits_{\substack{e \neq e' \\ e, e' \in E_s}} \sum \limits_{n = f(k_e)}^{g(e) - 1} \gamma^{g(e) - n} \cdot t(e', e, n) + \beta \sum \limits_{p \in P_l} \sum \limits_{\substack{e \in E \\ k_e \geq \sigma}} k_e \cdot q_e \cdot x(e, p)
minimize α s ∈ S ∑ e = e ′ e , e ′ ∈ E s ∑ n = f ( k e ) ∑ g ( e ) − 1 γ g ( e ) − n ⋅ t ( e ′ , e , n ) + β p ∈ P l ∑ e ∈ E k e ≥ σ ∑ k e ⋅ q e ⋅ x ( e , p ) 2. Phá tính đối xứng#
Vấn đề: Nhìn lại biến y ( e , r ) y(e, r) y ( e , r ) phòng nào trong số R R R được dùng
cho môn e e e r 1 , r 2 r_1, r_2 r 1 , r 2 r 1 r_1 r 1 r 2 r_2 r 2 e e e k k k k ! k! k !
Giải pháp: Thay vì hỏi "phòng nào", ta chỉ cần hỏi "bao nhiêu phòng
của một nhóm". Gọi một nhóm phòng là tập các phòng cùng loại, cùng sức chứa; G G G q g q_g q g c g c_g c g g g g y ( e , r ) y(e, r) y ( e , r ) z ( e , p , r ) z(e, p, r) z ( e , p , r )
u ( e , g ) = s o ˆ ˊ ph o ˋ ng nh o ˊ m g ph a ˆ n cho m o ˆ n thi e u(e, g) = \text{số phòng nhóm } g \text{ phân cho môn thi } e
u ( e , g ) = s o ˆ ˊ ph o ˋ ng nh o ˊ m g ph a ˆ n cho m o ˆ n thi e v ( e , p , g ) = s o ˆ ˊ ph o ˋ ng nh o ˊ m g ph a ˆ n cho m o ˆ n thi e v a ˋ o ca thi p v(e, p, g) = \text{số phòng nhóm } g \text{ phân cho môn thi } e \text{ vào ca thi } p
v ( e , p , g ) = s o ˆ ˊ ph o ˋ ng nh o ˊ m g ph a ˆ n cho m o ˆ n thi e v a ˋ o ca thi p Như vậy, mối liên hệ giữa các biến mới là v ( e , p , g ) = x ( e , p ) ⋅ u ( e , g ) v(e, p, g) = x(e, p) \cdot u(e, g) v ( e , p , g ) = x ( e , p ) ⋅ u ( e , g )
{ v ( e , p , g ) + q g ≤ q g ⋅ x ( e , p ) + u ( e , g ) q g ⋅ x ( e , p ) ≤ v ( e , p , g ) u ( e , g ) ≤ v ( e , p , g ) ∀ e ∈ E , p ∈ P , g ∈ G \begin{cases}
v(e, p, g) + q_g \leq q_g \cdot x(e, p) + u(e, g) \\
q_g \cdot x(e, p) \leq v(e, p, g) \\
u(e, g) \leq v(e, p, g)
\end{cases}
\quad \forall e \in E, p \in P, g \in G
⎩ ⎨ ⎧ v ( e , p , g ) + q g ≤ q g ⋅ x ( e , p ) + u ( e , g ) q g ⋅ x ( e , p ) ≤ v ( e , p , g ) u ( e , g ) ≤ v ( e , p , g ) ∀ e ∈ E , p ∈ P , g ∈ G Viết lại ràng buộc phòng thi. Ba ràng buộc về phòng thi ở Mục 1.2 được viết lại thành
u ( e , g ) = 0 , ∀ e ∈ E , g ∈ G e u(e, g) = 0, \quad \forall e \in E, g \in G_e
u ( e , g ) = 0 , ∀ e ∈ E , g ∈ G e ∑ g ∈ G c g ⋅ u ( e , g ) ≤ q e , ∀ e ∈ E \sum \limits_{g \in G} c_g \cdot u(e, g) \leq q_e, \quad \forall e \in E
g ∈ G ∑ c g ⋅ u ( e , g ) ≤ q e , ∀ e ∈ E ∑ e ∈ E v ( e , p , g ) ≤ q g , ∀ g ∈ G , p ∈ P \sum \limits_{e \in E} v(e, p, g) \leq q_g, \quad \forall g \in G, p \in P
e ∈ E ∑ v ( e , p , g ) ≤ q g , ∀ g ∈ G , p ∈ P 3. Mô hình hoàn chỉnh#
Gộp toàn bộ biến, ràng buộc và hàm mục tiêu ta có mô hình gốc của bài toán là
minimize α ∑ s ∈ S ∑ e ≠ e ′ e , e ′ ∈ E s ∑ n = f ( k e ) g ( e ) − 1 γ g ( e ) − n ⋅ t ( e ′ , e , n ) + β ∑ p ∈ P l ∑ e ∈ E k e ≥ σ k e ⋅ q e ⋅ x ( e , p ) subject to ∑ p ∈ P x ( e , p ) = 1 , ∀ e ∈ E ∑ e ∈ E s x ( e , p ) ≤ 1 , ∀ s ∈ S , p ∈ P x ( e , p ) = 0 , ∀ e ∈ E , p ∈ P e x ( e , p ) + ∑ q ∈ P ( p , f ( k e ) ) x ( e ′ , q ) ≤ 1 , ∀ s ∈ S , e ≠ e ′ ∈ E s , p ∈ P u ( e , g ) = 0 , ∀ e ∈ E , g ∈ G e ∑ g ∈ G c g ⋅ u ( e , g ) ≤ q e , ∀ e ∈ E ∑ e ∈ E v ( e , p , g ) ≤ q g , ∀ g ∈ G , p ∈ P v ( e , p , g ) + q g ≤ q g ⋅ x ( e , p ) + u ( e , g ) , ∀ e ∈ E , p ∈ P , g ∈ G q g ⋅ x ( e , p ) ≤ v ( e , p , g ) , ∀ e ∈ E , p ∈ P , g ∈ G u ( e , g ) ≤ v ( e , p , g ) , ∀ e ∈ E , p ∈ P , g ∈ G x ( e ′ , p ) + x ( e , p + n ) ≤ 1 + t ( e ′ , e , n ) , ∀ p , p + n ∈ P , s ∈ S , e ≠ e ′ ∈ E s , f ( k e ) ≤ n < g ( e ) x ( e , p ) ∈ { 0 , 1 } , ∀ e ∈ E , p ∈ P u ( e , g ) , v ( e , p , g ) ∈ Z ≥ 0 , ∀ e ∈ E , p ∈ P , g ∈ G t ( e ′ , e , n ) ∈ { 0 , 1 } , ∀ s ∈ S , e ≠ e ′ ∈ E s , f ( k e ) ≤ n < g ( e ) \begin{aligned}
\text{minimize} \quad
& \alpha \sum \limits_{s \in S} \sum \limits_{\substack{e \neq e' \\ e, e' \in E_s}} \sum \limits_{n = f(k_e)}^{g(e) - 1} \gamma^{g(e) - n} \cdot t(e', e, n)
+ \beta \sum \limits_{p \in P_l} \sum \limits_{\substack{e \in E \\ k_e \geq \sigma}} k_e \cdot q_e \cdot x(e, p) \\[0.9em]
\text{subject to} \quad
& \sum \limits_{p \in P} x(e, p) = 1, \quad \forall e \in E \\[0.6em]
& \sum \limits_{e \in E_s} x(e, p) \leq 1, \quad \forall s \in S, p \in P \\[0.6em]
& x(e, p) = 0, \quad \forall e \in E, p \in P_e \\[0.6em]
& x(e, p) + \sum \limits_{q \in P(p, f(k_e))} x(e', q) \leq 1, \quad \forall s \in S, e \neq e' \in E_s, p \in P \\[0.6em]
& u(e, g) = 0, \quad \forall e \in E, g \in G_e \\[0.6em]
& \sum \limits_{g \in G} c_g \cdot u(e, g) \leq q_e, \quad \forall e \in E \\[0.6em]
& \sum \limits_{e \in E} v(e, p, g) \leq q_g, \quad \forall g \in G, p \in P \\[0.6em]
& v(e, p, g) + q_g \leq q_g \cdot x(e, p) + u(e, g), \quad \forall e \in E, p \in P, g \in G \\[0.6em]
& q_g \cdot x(e, p) \leq v(e, p, g), \quad \forall e \in E, p \in P, g \in G \\[0.6em]
& u(e, g) \leq v(e, p, g), \quad \forall e \in E, p \in P, g \in G \\[0.6em]
& x(e', p) + x(e, p + n) \leq 1 + t(e', e, n), \quad \forall p, p + n \in P, s \in S, e \neq e' \in E_s, f(k_e) \leq n < g(e) \\[0.6em]
& x(e, p) \in \{0, 1\}, \quad \forall e \in E, p \in P \\[0.6em]
& u(e, g), v(e, p, g) \in \mathbb{Z}_{\geq 0}, \quad \forall e \in E, p \in P, g \in G \\[0.6em]
& t(e', e, n) \in \{0, 1\}, \quad \forall s \in S, e \neq e' \in E_s, f(k_e) \leq n < g(e)
\end{aligned}
minimize subject to α s ∈ S ∑ e = e ′ e , e ′ ∈ E s ∑ n = f ( k e ) ∑ g ( e ) − 1 γ g ( e ) − n ⋅ t ( e ′ , e , n ) + β p ∈ P l ∑ e ∈ E k e ≥ σ ∑ k e ⋅ q e ⋅ x ( e , p ) p ∈ P ∑ x ( e , p ) = 1 , ∀ e ∈ E e ∈ E s ∑ x ( e , p ) ≤ 1 , ∀ s ∈ S , p ∈ P x ( e , p ) = 0 , ∀ e ∈ E , p ∈ P e x ( e , p ) + q ∈ P ( p , f ( k e )) ∑ x ( e ′ , q ) ≤ 1 , ∀ s ∈ S , e = e ′ ∈ E s , p ∈ P u ( e , g ) = 0 , ∀ e ∈ E , g ∈ G e g ∈ G ∑ c g ⋅ u ( e , g ) ≤ q e , ∀ e ∈ E e ∈ E ∑ v ( e , p , g ) ≤ q g , ∀ g ∈ G , p ∈ P v ( e , p , g ) + q g ≤ q g ⋅ x ( e , p ) + u ( e , g ) , ∀ e ∈ E , p ∈ P , g ∈ G q g ⋅ x ( e , p ) ≤ v ( e , p , g ) , ∀ e ∈ E , p ∈ P , g ∈ G u ( e , g ) ≤ v ( e , p , g ) , ∀ e ∈ E , p ∈ P , g ∈ G x ( e ′ , p ) + x ( e , p + n ) ≤ 1 + t ( e ′ , e , n ) , ∀ p , p + n ∈ P , s ∈ S , e = e ′ ∈ E s , f ( k e ) ≤ n < g ( e ) x ( e , p ) ∈ { 0 , 1 } , ∀ e ∈ E , p ∈ P u ( e , g ) , v ( e , p , g ) ∈ Z ≥ 0 , ∀ e ∈ E , p ∈ P , g ∈ G t ( e ′ , e , n ) ∈ { 0 , 1 } , ∀ s ∈ S , e = e ′ ∈ E s , f ( k e ) ≤ n < g ( e ) Đây là mô hình mô tả đúng và đủ bài toán xếp lịch thi. Khi viết xong mô hình này mình tràn đầy hi vọng vào kết quả khi
đưa vào máy tính để giải, và đó cũng chính là lúc vấn đề lớn nhất của nghiên cứu xuất hiện. Hãy đọc phần tiếp theo để biết
vấn đề đó là gì và mình đã giải quyết nó như thế nào nhé.
Đọc tiếp Phần 4
TungTT