Admin đã viết:Bây giờ giải đề thi năm 2010 [You must be registered and logged in to see this link.]
IV. Tìm các lịch gia công tối ưu và vẽ sơ đồ Gantt cho bài toán 2 máy, thời gian gia công các chi tiết trên 2 máy cho trong bảng sau:

Chi tiết Máy	D1	D2	D3	D4	D5
A	6	8	4	7	8
B	7	5	6	4	5

1. Chia các chi tiết ra làm 2 nhóm:
          a) Nhóm N₁ gồm những chi tiết D_i thoả mãn a_i < b_i, ta có N₁ = (D₁, D₃)
          b) Nhóm N₂ gồm những chi tiết D_i thoả mãn a_i > b_i, ta có = (D₂, D₄, D₅)

2. Sắp xếp các chi tiết trong:
          a) N₁ → theo chiều tăng các a_i ta có N₁ = (D₃ , D₁) do a₃ < a₁,(a₃ = 4, a₁ = 6)
          b) N₂ → theo chiều giảm các b_i do b₂ =b₅ > b₄, nên ta sẽ có 2 phương án, do có thể đổi chỗ b₂ =b₅ cho nhau. Ta có:
                    N₂₁ = (D₂, D₅, D₄)
                    N₂₂ = (D₅, D₂, D₄)

3. Viết: Lịch gia công tối ưu là 2 phương án sau:
          a) Dãy N_{tối_ưu_1} = (D₃ , D₁, D₂, D₅, D₄)
          b) Dãy N_{tối_ưu_2} = (D₃ , D₁, D₅, D₂, D₄)

4. Vẽ bằng sơ đồ Gantt:
Có nhiều phần mềm online vẽ sơ đồ Gantt trên mạng, nhưng ở đây được viết ra để Khách viếng thăm hiểu từng bước, nên không sử dụng các trang hỗ trợ vẽ sơ đồ Gantt đó. Cách vẽ từng bước như sau:
Bước 1. Kẻ một trục toạ độ, nhưng không dùng mũi tên ở 2 đầu nha. khoảng 5 dòng. Trục tung gõ chữ Máy, trục hành gõ chữ t. Ở trục tung, dành 2 dòng dưới để vẽ cho máy A, 2 dòng trên vẽ theo máy B. Nên đánh chữ A và B, đừng kẻ vội không xấu.
Bước 2. Chia trục hoành ra làm nhiều phần. Số phần cần lớn hơn ∑ (a_i) khoảng 5 đến 10 vạch. Ở bài toán này ta có ∑ = 6 + 8 + 4 + 7 + 8 = 33, nên Khách viếng thăm hãy vẽ khoảng 40 vạch.
Bước 3. Xếp lần lượt cách khối là các giá trị của a_i theo dãy gia công tối ưu ở phần 3. Ở đây ta vẽ theo dãy N_{tối_ưu_1} còn dãy tối ưu N_{tối_ưu_2} thì sau đó Khách viếng thăm hãy tự vẽ.
Hết bước này trông sơ đồ Gantt sẽ như thế này:
[You must be registered and logged in to see this image.]
Bước 4.Sắp xếp các chi tiết Di của máy B sao cho, b_i phải bắt đầu sau khi a_i kết thúc rồi. Nếu kết thúc trước đó thì OKnối luôn vào, còn chưa xong thì bắt đầu từ khi chi tiết của a_i kết thúc. Khoảng trống tô đen đi. Xong. Chú ý vẽ ra nháp để tránh thừa các đầu nom rất xấu. Ta sẽ có kết quả như vầy:
[You must be registered and logged in to see this image.]