Bài toán lập lịch gia công trên hai máy năm 2024

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 A68478B7 5 64 5

1. Chia các chi tiết ra làm 2 nhóm:

1. Nhóm N1 gồm những chi tiết Di thoả mãn ai < bi, ta có N1 = (D1, D3)
2. Nhóm N2 gồm những chi tiết Di thoả mãn ai > bi, ta có = (D2, D4, D5)

2. Sắp xếp các chi tiết trong:

1. N1 → theo chiều tăng các ai ta có N1 = (D3 , D1) do a3 < a1,(a3 = 4, a1 = 6)
2. N2 → theo chiều giảm các bi do b2 \=b5 \> b4, nên ta sẽ có 2 phương án, do có thể đổi chỗ b2 \=b5 cho nhau. Ta có:

   N21 = (D2, D5, D4) N22 = (D5, D2, D4)

   3. Viết: Lịch gia công tối ưu là 2 phương án sau:
3. Dãy Ntối_ưu_1 = (D3 , D1, D2, D5, D4)
4. Dãy Ntối_ưu_2 = (D3 , D1, D5, D2, D4)

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 ∑ (ai) 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

ai theo dãy gia công tối ưu ở phần 3. Ở đây ta vẽ theo dãy Ntối_ưu_1 còn dãy tối ưu Ntố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, bi phải bắt đầu sau khi ai 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 ai 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.]

Bai Toan Lap Lich

Uploaded by

ctlatd2

100% found this document useful (2 votes)

88 views

3 pages

Original Title

BaiToanLapLich

Copyright

© Attribution Non-Commercial (BY-NC)

Available Formats

DOC, PDF, TXT or read online from Scribd

Share this document

Did you find this document useful?

Is this content inappropriate?

100% found this document useful (2 votes)

88 views3 pages

Bai Toan Lap Lich

Uploaded by

ctlatd2

Jump to Page

You are on page 1of 3

Search inside document

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

Nội dung Text: Bài toán lập lịch

1. I. Một số thuật toán 1.Thuật toán Johnson Bài toán 1: 'Mỗi một chi tiết D1,D2,...Dn cần phải được lần lượt gia công trên 2 máy A,B. Thời gian gia công chi tiết Di trên máy A là ai trên máy B là bi (i=1,2..n). Hãy tìm lịch (trình tự gia công) các chi tiết trên hai máy sao cho việc hoàn thành gia công tất cả các chi tiết là sớm nhất'. Thuật Johnson: Chia các chi tiết thành 2 nhóm: nhóm N1, gồm các chi tiết Di thoả mãn a1 bi tức là min(ai,bi)=bi. Các chi tiết Di thoả mãn ai =bi xếp vào nhóm nào cũng được. Sắp xếp các chi tiết trong N1 theo chiều tăng của các ai và sắp xếp các chi tiết trong N2 theo chiều giảm của các bi Nối N2 vào đuôi N1, dãy thu được (đọc từ trái sang phải) sẽ là lịch gia công. Bài toán 2: '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 ai,bi,ci,i=1,2,..n thoả mãn: max bi ≤ min ai hoặc max bi ≤ min ci' 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 ai + bi và máy thứ hai với thời gian bi + c i. 2. Thuật toán More Bài toán: 'Có n ôtô đưa vào xưởng sửa chữa được đánh số thứ tự 1,2..,n. Ôtô phải sửa chữa trong thời gian ti và thời điểm phải bàn giao là di. Mỗi thời điểm xưởng chỉ sửa chữa một cái, xưởng sửa chữa không ngừng và thời điểm bắt đầu sửa chữa là 0. Hãy đưa ra một thứ tự sữa chữa sao cho số lượng ôtô đúng hạn là lớn nhất.' Sắp xếp theo thứ tự tăng dần của thời điểm bàn giao Duyệt từ đầu cho đến khi gặp ôtô quá hạn đầu tiên (Giả sử là ôtô thứ k) Tìm từ đầu cho đến ôtô thứ k, ôtô nào có ti lớn nhất (Giả sử đó là ôtô thứ m). Nếu ôtô này đã được chuyển một lần rồi thì dừng chương trình, còn nếu không thì ta chuyển ôtô này xuống cuối. Rồi trở lại bước 2. 3. Các phương pháp khác: Thông thường thì các bài toán dạng này thường có rất nhiều cách giải. Nhưng thông dụng nhất là thuật toán quy hoạch động và duyệt nhánh cận. Ngoài ra một số còn đưa về đồ thị. II. Bài tập Bài 1: Lập lịch ưu tiên đúng hạn Đề bài:
2. Có n công việc đánh số từ 1 đến n và một máy để thực hiện chúng. Biết: ­ p1 là thời gian cần thiết để hoàn thành công việc j. ­ di là thời hạn hoàn thành công việc i. Mỗi công việc cần được thực hiện liên tục từ lúc bắt đầu cho tới khi kết thúc, không cho phép ngắt quãng. Khoảng thời gian thực hiện hai công việc bất kỳ chỉ được có nhiều nhất 1 điểm chung. Giả sử C1 là thời điểm hoàn thành trễ hạn, còn nếu Ci
3. inc(shd); st[shd]:=x; if time+p[x]
4. end; procedure khoitao; begin fillchar(tt,sizeof(tt),0); fillchar(roi,sizeof(roi),false); end; procedure xuly; var j,min,cs,t,k,i:integer; ok1,ok2:boolean; begin ok1:=false; ok2:=false; k:=0; t:=0; for j:=1 to n do begin min:=maxint; for i:=1 to n do begin if (min>a[i]) and (roi[i]=false) then begin cs:=i; min:=a[i]; ok2:=false; ok1:=true; end; if (min>b[i]) and (roi[i]=false) then begin cs:=i; min:=b[i]; ok1:=false; ok2:=true; end; end; roi[cs]:=true; if ok1=true then begin k:=k+1; tt[k]:=cs; end else begin tt[n-t]:=cs; t:=t+1; end; end; end; procedure calc; var sa,i:integer; begin sa:=a[tt[1]]; sb:=a[tt[1]]+b[tt[1]];
5. for i:=2 to n do begin sa:=sa+a[tt[i]]; if sa>=sb then sb:=sa+b[tt[i]] else sb:=sb+b[tt[i]]; end; end; procedure output; var i:integer; begin assign(f,fo); rewrite(f); writeln(f,sb); for i:=1 to n do write(f,tt[i],' '); close(f); end; BEGIN clrscr; input; khoitao; xuly; calc; output; END. Bài toán lập lịch là 1 bài toán khó, trên đây mình chỉ giới thiệu với các bạn 2 thuật toán cơ bản của bài toán lập lịch. Nếu bạn nào quan tâm thì cứ gửi mail cho mình, mình có rất nhiều bài tập nữa liên quan đến phần này.