Bài toán lập lịch

Bài toán lập lịch

Nguyễn Thế Anh

I.Một số thuật toán

1.Thuật toánJohnson

Bàitoán 1:

'Mỗi một chi tiết D1,D2,…Dn cần phải được lần lượt gia côngtrê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áyB là bi (i=1,2..n). Hãy tìm lịch (trình tự gia công)

các chi tiết trênhai máy sao cho việc hoàn thành gia công tất cả các chi tiết là sớmnhất'.

Thuật Johnson:

Chia các chi tiết thành2 nhóm: nhóm N1, gồm các chi tiết Di thoả mãn a1 < b1, tức

làmin(ai,bi) = ai và nhóm N2 gồm các chi tiết Di thoả mãn ai >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ếttrong N1 theo chiều tăng của các ai và sắp xếp các chi tiết trong N2theo

chiều giảm của các bi

Nối N2 vào đuôi N1, dãythu được (đọc từ trái sang phải) sẽ là lịch gia công.

Bàitoá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ảngthời gian

ai,bi,ci,i=1,2,..n thoả mãn:

maxbi ≤ min ai hoặc max bi ≤ min ci

'

Thuậttoá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ờigian ai + bi và máy thứ hai với thời gian bi + c i.

2.Thuật toán More

Bàitoá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 tivà 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 theothứ 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ừ đầucho đế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ươngtrình, còn nếu không thì ta chuyển ôtô này xuống

cuối. Rồi trở lạibước 2.

3. Các phươngpháp khác:

Thôngthườ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ậplịch ưu tiên đúng hạn

Đề bài:

Có n công việc đánh số từ 1 đếnn và một máy để thực hiện chúng. Biết:

- p1 là thờigian cần thiết để hoàn thành công việc j.

- di là thờihạn hoàn thành công việc i.