Em gửi một số đề thi liên quan đến dạng này để mọi người tham khảo và có hướng giải.

Câu 4. Đề thi năm 2009:
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	9	4	6	10	8
B	7	3	8	10	6

Câu 4. Đề thi năm 2008:
Tìm 3 (nếu 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	8	5	6	5	7
B	9	3	7	5	6

Câu 4. Đề thi năm 2006:
Tìm 3 (nếu 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	4	7	6	12	7
B	5	8	8	9	7

Thuật toán Johnson để làm việc với các bài toán dạng này
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, tức là min(a_i , b_i) đạt được tại a_i
          b) Nhóm N₂ gồm những chi tiết D_i thoả mãn a_i > b_i, tức là min(a_i , b_i) đạt được tại b_i
          c) Các chi tiết D_i thoả mãn a_i = b_i xếp vào nhóm nào cũng được.

2. Sắp xếp các chi tiết trong:
          a) N₁ → theo chiều tăng các a_i
          b) N₂ → theo chiều giảm các b_i

3. Viết:
          a) Dãy N₁
          b) rồi viết N₂ nối tiếp vào sau dãy trên. Dãy thu được (đọc từ trái qua phải) sẽ là lịch gia công tối ưu.

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

Thêm thời gian hoàn thành việc gia công là chuẩn luôn!

T(N_{tối_ưu_1})= 37

Theo tôi, hết bước bước 3 (theo đ/c Lớp trưởng, tức là trước khi vẽ sơ đồ Grantt)chúng ta nên vẽ lại bảng theo phương án tối ưu cho đỡ nhầm khi tính T(π), và nên viết các bước tính T(π) cẩn thận nữa.

Admin: Tức là trước khi vẽ sơ đồ, sẽ kẻ lại cái bảng sau khi đã sắp xếp là:

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

OK.

Giới thiệu cả lớp bài toán sau.

Hãy lập lịch gia công cho 2 máy như sau:

	D1	D2	D3	D4	D5
Máy A	5	6	7	3	6
Máy B	6	4	7	4	4
Tg	2	1	3	2	3

Trong đó, Tg là thời gian để chuyển chi tiết Di từ máy A sang máy B

Bài toán

Xét bài toán gia công N chi tiết trên 3 máy theo thứ tự A, B, C với bảng thời gian a_i, b_i, c_i, i = 1 , 2,.. n thoả mãn:
max b_i ≤ min a_i hoặc max b_i ≤ min c_i.

Thuật toán:

Lịch gia công tối ưu trên 3 máy sẽ trùng với lịch gia công tối ưu trên 2 máy: máy thứ nhất với thời gian a_i + b_i và máy thứ hai với thời gian b_i + c_i.



- Bài toán này có đúng không mọi người nhỉ. Ai có sách Giáo khoa (không phải tài liệu ôn thi đâu) thử kiểm tra lại cho mình nhé.

Thưa thầy. Thầy cho em hỏi trong thời gian chuyển chi tiết Di từ máy A sang máy B thì các máy A và B có làm việc bình thường hay không ạ?

Trong khoảng thời gian chuyển chi tiết Di từ máy A sang máy B, các máy vẫn đang hoạt động bình thường nếu có thể.
Lưu ý, bài toán lập lịch gia công trên 3 máy rất phức tạp khi làm bằng tay. Các bạn cố gắng chuyển về dạng lập lịch gia công trên 2 máy nhé.

Gợi ý: coi như lập lịch gia công trên 2 máy, với thời gian trên máy B đã hiệu chỉnh thêm thông tin của Tg.

Bài này bạn có thể sử dụng các phần mềm hiện có trong máy tính để vét cạn tất cả 120 trường hợp. Tôi có thể lấy ví dụ một số phần mềm thông dụng là MS Project, Ms OutLook, Ms Access thậm chí lập trình với VBA trong Word hoặc Excel cũng được. Tôi dùng MS Excel để có bản sau:

Từ bảng này ta phải có được 2 phương án tối ưu với thời gian hoàn thành là 33.
Bây giờ các bạn hãy trổ tài lý luận và kết hợp lý thuyết để chỉ ra 2 phương án trên cùng đó nha.
Bạn nào có nhu cầu, tôi sẽ send cho file EXCEL để nghiên cứu. Bạn chỉ việc nhập vào các giá trị của bảng mà thầy giáo ra, chương trình sẽ tự đưa ra phương án tối ưu bằng thuật toán vét cạn. File này tôi vừa viết xong cách đây vài phút, chưa tinh chỉnh. Còn nếu cần tinh chỉnh hoặc viết bằng C thì phải chờ tôi dùng máy khác, máy này của tôi không cài các phần mềm lập trình, nên dùng tạm vài cái công cụ con con của MS làm tạm.
[You must be registered and logged in to see this link.]

Thưa thầy, theo cách thầy gợi ý, ta có cần chứng minh cách đấy là tối ưu không ah?

anh chị cho em hỏi chút...đề 2006, và đề 2009 ý ạ..em lấy ví dụ đề 2009 đi, cái D4 của cả 2 máy đều bằng 10, tức là ta sẽ phải chia thành 2 trường hợp là TH1 a4 > b4 và TH2 a4
Admin: Đọc kỹ lý thuyết chưa nhỉ?

anh Admin hỏi thế thì chắc em phải tự tìm hiểu rồi...em ko có dc đi học ôn vì làm việc ở xa...và dưới đây em cũng có ít sách tham khảo quá...bác thông cảm...công tác vùng cao khổ thế đấy.

Add:
Ok! Đã tìm thấy, Nếu Di thỏa mãn ai=bi thì xếp vào nhóm nào cũng đc...ai biết rồi thì đừng cười, còn ai chưa biết thì rút knghiem nha...kẻo như em chia làm 2 TH, cẩn thận quá hóa thừa..lại quá dài

mrP đã viết:Bài toán

Xét bài toán gia công N chi tiết trên 3 máy theo thứ tự A, B, C với bảng thời gian a_i, b_i, c_i, i = 1 , 2,.. n thoả mãn:
max b_i ≤ min a_i hoặc max b_i ≤ min c_i.

Thuật toán:

Lịch gia công tối ưu trên 3 máy sẽ trùng với lịch gia công tối ưu trên 2 máy: máy thứ nhất với thời gian a_i + b_i và máy thứ hai với thời gian b_i + c_i.





- Bài toán này có đúng không mọi người nhỉ. Ai có sách Giáo khoa (không phải tài liệu ôn thi đâu) thử kiểm tra lại cho mình nhé.

Chính xác, nhận xét trên được trích trong Toán rời rạc của Nguyễn Đức Nghĩa, Nguyễn Tô Thành, chú ý chỉ có lịch tối ưu của chúng là trùng nhau còn thời gian gia công là khác nhau.

Ngo Huu Phuc đã viết:Trong khoảng thời gian chuyển chi tiết Di từ máy A sang máy B, các máy vẫn đang hoạt động bình thường nếu có thể.
Lưu ý, bài toán lập lịch gia công trên 3 máy rất phức tạp khi làm bằng tay. Các bạn cố gắng chuyển về dạng lập lịch gia công trên 2 máy nhé.

Gợi ý: coi như lập lịch gia công trên 2 máy, với thời gian trên máy B đã hiệu chỉnh thêm thông tin của Tg.

Theo như sách của Nguyễn Đức Nghĩa và Nguyễn Tô Thành, khi chuyển về bài toán 2 máy thì phải hiệu chỉnh cả thời gian của A và B theo Tg. Em đã giải đề bài thầy đưa, nếu chỉ hiệu chỉnh B thì phương án tối ưu là:D4, D1, D5, D3, D2 với tổng thời gian là 36, trong khi nếu hiệu chỉnh cả A và B theo tg, phương án tối ưu là: D4, D1, D3, D5, D2, tổng thời gian là 33, rõ ràng tối ưu hơn. vậy em nghĩ bài toán này phải hiệu chỉnh cả A và B.

Cảm ơn em Hiền nhé, đúng là anh đang băn khoăn không biết phải giải cách nào. Anh là chúa lười nên không muốn thử đi thử lại, may mà có em chịu khó kiểm tra. Hi vọng là bài toán kiểu như thế này sẽ không thi.

	D1	D2	D3	D4	D5
Máy A	5	6	7	3	6
Máy B	6	4	7	4	4
Tg	2	1	3	2	3

Admin cho hỏi với bài toán như vậy tìm ra đáp án là D4, D1, D3, D5, D2 thì các thời gian tương ứng là khi ở máy A : D4 = 3; D1=5;D3=7 và khi ở máy B là D5 = 4; D2 = 4vậy tổng thời gian làm việc là : 3+5+7+4+4 = 23 và thời gian chuyển là 2+2+3+3 = 10 thì tổng thời gian mới là 33.
Tuy nhiên mình có thắc mắc là D4;D1;D3 đang làm ở máy A thì chuyển sang máy B làm gì ? và D5 đang làm máy B thì chuyển sang máy A làm gì? (vì ta tính cả tổng thời gian chuyển của chi tiết đó mà)?
Và nếu đúng phải chuyển như vậy thì tại sao không phải là D4, D1, D3, D2, D5 thì thời gian chuyển chỉ còn 2+2+3+1 = 8 và tổng thời gian là 31 ==> tối ưu hơn hẳn?
Mong Khách viếng thăm giải đáp thắc mắc sớm một chút, mình ở K24 sắp thi đến nơi rồi

Thầy giáo Ngô Hữu Phúc đã giải thích

Ngo Huu Phuc đã viết:Trong khoảng thời gian chuyển chi tiết Di từ máy A sang máy B, các máy vẫn đang hoạt động bình thường nếu có thể.
Lưu ý, bài toán lập lịch gia công trên 3 máy rất phức tạp khi làm bằng tay. Các bạn cố gắng chuyển về dạng lập lịch gia công trên 2 máy nhé.

Gợi ý: coi như lập lịch gia công trên 2 máy, với thời gian trên máy B đã hiệu chỉnh thêm thông tin của Tg.

Đây là một bài toán rất phức tạp, bạn không nên phí sức với bài này. nên tập trung ôn những bài lập lịch gia công trên 2 máy. mà đề các năm đã có nhé!

Phương pháp giải một bài toán lập lịch gia công trên hai máy như sau:
[You must be registered and logged in to see this image.]

Đáp án câu 4 - Đề thi Cao học năm 2011 như sau:

[You must be registered and logged in to see this image.]

Anh Đức đã viết:Đáp án câu 4 - Đề thi Cao học năm 2011 như sau:

[You must be registered and logged in to see this image.]

anh cho em hỏi là tại sao tổng time =36?; theo em nghĩ T=D4+D3+D1+D5+D2+(a4-a3)+(a3-a1)+(a1-b5)+(b5-b2)=4+6+8+6+3+2+2+2+3=36 "?"
Em đang tự mầy mò học, em không hiểu có đúng vậy ko?, mong anh và các bạn chỉ giúp. thanks.

Ban QT: Đọc lại bài học từ đầu đi ông mãnh.
Sắp xếp gia công, có những việc phải làm xong thì mới làm được việc khác. Ví dụ như phải làm xong khuôn, sau đấy mới thực hiện đúc được... cho nên có thời gian nghỉ (bỏ không 1 máy, để chờ máy kia xong mới làm được → thời gian dài ra), chứ không phải người ta cộng thời gian như học sinh lớp 1.

bài đọc rất hay, thank all

Cảm ơn Anh Đức nhiều.

Thanks you very FOR all !!!

Anh Đức đã viết:Đáp án câu 4 - Đề thi Cao học năm 2011 như sau:

[You must be registered and logged in to see this image.]

cái này tính T ntn vậy ạ?