Nội dung Trang
PHẦN I. MỞ ĐẦU
1. Lý do chọn đề tài
2. Mục đích của sáng kiến kinh nghiệm
3. Đối tượng và phạm vi nghiên cứu
4. Cơ sở khoa học của đề tài
PHẦN II. NỘI DUNG
Chương 1. Ứng dụng một số thuật toán, định lí vào việc giải các bài
toán về xếp lịch
1. Xét bài toán xếp lịch
2. Ứng dụng một số thuật toán vào giải các bài toán xếp lịch
a. Thuật toán Johnson
b. Phương pháp Heuristic.
c. Phương pháp duyệt có đặt cận
d. Quy hoạch động
e. Phương pháp làm mịn dần phương án
f. Thuật toán tối ưu cho một số bài đặc biệt
g. Phương pháp thế vị
h. Phương pháp dựa vào luồng và đồ thị hai phía
Chương 2. Một số bài tập về sắp xếp lịch
PHẦN III. KẾT LUẬN VÀ KIẾN NGHỊ
2
2
2
2
4
8
8
11
16
20

- Đưa vào tài liệu của tổ chuyên môn.
3. Đối tượng và phạm vi nghiên cứu:
3.1 Đối tượng nghiên cứu:
- Các bài toán về xếp lịch để giảng dạy cho học sinh đi thi học sinh giỏi tỉnh.
3.2 Phạm vi nghiên cứu:
2
- Với các thuật toán, định lí, các bài toán, tôi áp dụng vào dạy học sinh ôn thi học
sinh giỏi tỉnh.
4. Cơ sở khoa học của đề tài:
4.1 Cơ sở lí luận:
Các bài toán về xếp lịch được ứng dụng rất nhiều trong thực tiễn, với sự phát triển
của CNTT như hiện nay thì việc áp dụng CNTT vào các cơ quan tổ chức là một việc
làm đúng đắn, mà công việc xếp lịch rất phổ biến
4.2 Cơ sở thực tiễn:
- Đây là bài toán có nhiều ứng dụng trong thực tiễn, từ những bài sắp xếp lịch công
việc đơn giản đến các công việc phức tạp hơn như xếp thời khóa biểu của một trường
học,…
3
NỘI DUNG SÁNG KIẾN KINH NGHIỆM
CHƯƠNG 1. ỨNG DỤNG MỘT SỐ THUẬT TOÁN, ĐỊNH LÍ VÀO VIỆC
GIẢI CÁC BÀI TOÁN VỀ XẾP LỊCH
1. Xét bài toán xếp lịch sau:
Giả sử trong một phiên làm việc từ thời điểm 0 đến thời điểm T=8640000, một
trung tâm tính toán phải thực hiện N chương trình, chương trình i thực hiện từ thời
điểm a[i] đến thời điểm b[i],
0 [ ] [ ]a i b i T≤ ≤ <
.
Cho trước một đoạn thời gian (P
1
, Q

1
, S
1
(
1 1
R S≤
)
Dữ liệu ra ghi vào file văn bản LICHTRUC.OUT có cấu trúc
- Dòng đầu tiên ghi 1 hoặc 0 tùy thuộc kết quả cụ thể (tìm được ghi số 1, không
tìm được ghi số 0).
- Dòng thứ hai cũng ghi 1 hoặc 0 theo nghĩa trên.
- Dòng thứ ba ghi hai số P, Q
- Dòng thứ tư ghi hai số R, S.
4
Ví dụ:
LICHTRUC.INP LICHTRUC.OUT
5
1000 10000
2000 20000
20000 100000
200000 500000
8000000 8500000
1000 100000
0 1000
1
0
8000000 8500000
500001 7999999
Nhận xét: Để giải bài toán này thì ta có thể dùng mảng một chiều A (mỗi phần tử
là một bản ghi gồm 2 trường: thời điểm đầu và thời điểm cuối của mỗi chương trình).

end;
procedure sort;
var i,j:integer;
tgd,tgc:longint;
begin
5
for i:=1 to n -1 do
for j:=i+1 to n do
if a[i].d>a[j].d then
begin
tgd:=a[i].d;
a[i].d:=a[j].d;
a[j].d:=tgd;
tgc:=a[i].c;
a[i].c:=a[j].c;
a[j].c:=tgc;
end;
end;
procedure Create_b_c;
var i,j:integer;
last:longint;
begin
sd:=1;
i:=1;
b[sd].d:=a[i].d;
last:=a[i].c;
while i<n do
begin
if a[i+1].d>last+1 then
begin

c[sr].d:=b[sd].c+1;
c[sr].c:=t;
end;
end;
procedure caua;
6
var i:integer;
begin
for i:=1 to sd do
if (b[i].d<=p) and (b[i].c>=q) then
begin
writeln(f,1);
exit;
end;
writeln(f,0);
end;
procedure caub;
var i:integer;
begin
for i:=1 to sr do
if (c[i].d<=r) and (c[i].c>=s) then
begin
writeln(f,1);
exit;
end;
writeln(f,0);
end;
procedure cauc;
var ld,lc,lmax:longint;
i:integer;

create_b_c;
caua;
caub;
cauc;
caud;
7
close(f);
end.
2. ứng dụng một số thuật toán vào giải các bài toán xếp lịch
a. Dựng thut toỏn Johnson
Vớ d: Lp lch gia cụng trờn hai mỏy
Mt sn phm gm N chi tit, mi chi tit phi gia cụng ln lt trờn hai mỏy A v
B (A trc, B sau). Thi gian thc hin chi tit i trờn mỏy A l A
i
, trờn mỏy B l B
i
(i=1, 2, , N). Hóy xp lch hon thnh sn phm vi thi gian ớt nht. Hin lch v
thi gian hon thnh.
D liu vo t file GIACONG.INP cú cu trỳc:
- Dũng u tiờn l s nguyờn dng N
- N dũng tip theo: dũng i+1 l hai s A
i
v B
i
.
D liu ra ghi vo file GIACONG.OUT cú cu trỳc:
- Dũng u tiờn l thi gian ớt nht thc hin N cụng vic
- Dũng th hai ln lt ghi s hiu ca N cụng vic thc hin theo lch ti u.
Vớ d:
GIACONG.INP GIACONG.OUT

v B
v[k+1
]
tng ng l thi gian thc hin v[k] v v[k+1]
trờn mỏy B.
8
Từ định lí trên có thể đưa ra thuật toán để giải bài toán trên, và chứng minh sự đúng
đắn của thuật toán sau:
* Thuật toán:
+ Bước 1: Chia các chi tiết thành hai nhóm:
Nhóm 1: gồm các chi tiết i mà
i i
A B≤
.
Nhóm 2: gồm các chi tiết i mà
i i
A B>
+ Bước 2: Xếp nhóm 1 theo chiều tăng của A
i
, xếp nhóm 2 theo chiều giảm của B
i
.
+ Bước 3: Nối nhóm 2 vào sau nhóm 1
* Chứng minh:
Nếu các chi tiết v[k] và v[k+1] cùng thuộc nhóm 1 thì
[ 1] [ 1] [ ]v k v k v k
B A A
+ +
≥ ≥
nên

v[k+1]
}
Nếu chi tiết v[k] và v[k+1] cùng thuộc nhóm 2 thì
[ 1] [ ] [ ]v k v k v k
B B A
+
≤ <
nên Min {A
[k]
,
B
v[k]
}=B
v[k+1]
mặt khác
[ ] [ 1] [ 1] [ 1]
,
v k v k v k v k
B B A B
+ + +
≥ ≥
nên Min {B
v[k]
, A
v[k+1]
}
≥
B
v[k+1]
. Vậy

< A
v[k+1]
.
có thể thực hiện cụ thể như sau: Xây dựng dần dãy kết quả từ hai đầu dồn vào giữa
(dùng mảng một chiều KQ và hai biến: đầu và cuối).
1. Gán giá trị ban đầu: đầu:=0; cuối:=N+1;
2. Thực hiện vòng lặp: trong khi đầu < cuối
a. Tìm chi tiết i chưa làm, có thời gian thực hiện nhỏ nhất.
b. Nếu i thuộc dãy A thì tăng giá trị biến đầu, gán KQ[đầu]:=i, nếu i thuộc dãy
B thì giảm giá trị biến cuối, gán KQ[cuối]:=i;
3. Đánh dấu đã làm chi tiết i.
Cµi ®Æt ch¬ng tr×nh:
const max=100;
fi='giacong.inp';
fo='giacong.out';
9
type m1=array[1 2,1 max] of integer;
mkq=array[1 max] of byte;
mdd=array[1 max] of boolean;
var a:m1;
kq:mkq;
dd:mdd;
n:byte;
g,f:text;
procedure readfile;
var i:byte;
begin
assign(f,fi);
reset(f);
readln(f,n);

inc(dau);
kq[dau]:=chitiet;
dd[chitiet]:=true;
end
else
begin
dec(cuoi);
kq[cuoi]:=chitiet;
dd[chitiet]:=true;
end;
until dau=cuoi-1;
end;
procedure writefile;
var i:byte;
begin
10
for i:=1 to n do
if dd[i] then write(g,kq[i],' ');
end;
function max2(a,b:integer):integer;
begin
if a>b then max2:=a else max2:=b;
end;
procedure tinh;
var i,j:byte;
t1, t2:integer;
begin
t1:=0; t2:=0;
for i:=1 to n do
begin

Ví dụ: Cho phép tổng chi phí (hoặc tổng thời gian) thực hiện xong các công việc đạt
giá trị càng thấp càng tốt (hoặc xong càng sớm càng tốt). Chính nhờ sự nhân nhượng
này mà ta có thể đề xuất ra những cách sắp xếp một hoặc một nhóm công việc tiếp
theo dễ dàng hơn, đó chính là các “heuristic”.
Thuật giải heuristic có những đặc điểm sau:
- Cho lời giải gần tối ưu, thời gian thực hiện chương trình là hợp lí và có thể tổ
chức dữ liệu để thực hiện chương trình.
- Có thể thay đổi một vài heuristic trong quá trình giải để thích ứng với các bộ dữ
liệu khác nhau, kết hợp so sánh kết quả thực hiện các heuristic khác nhau và giữ lại
kết quả tốt hơn.
Ví dụ: Chia N việc cho M máy
Cho N công việc, công việc i hoàn thành trong thời gian t
i
. Các công việc được
thực hiện trên M máy (công suất như nhau, mỗi máy đều có thể thực hiện được công
việc bất kì trong N công việc) mỗi công việc được làm liên tục trên một máy cho đến
khi xong. Hãy tổ chức máy thực hiện đủ N công việc sao cho thời gian hoàn thành
càng nhỏ càng tốt.
Dữ liệu vào từ file CHIA.INP có cấu trúc:
- Dòng đầu là hai số N và M.
- Dòng tiếp theo là N số t
1
, t
2
, …, t
N
.
Dữ liệu ra ghi vào file CHIA.OUT có cấu trúc:
- Dòng đầu là thời gian hoàn thành N công việc.
- M dòng sau: dòng i+1 ghi số hiệu các công việc thực hiện trên máy i

Lần phân công thứ nhất:
Máy 1: cv3=8 đơn vị thời gian
Máy 2: cv2=5 đơn vị thời gian
Máy 3: cv5=5 đơn vị thời gian
13
Như vậy máy làm công việc có thời gian làm lớn nhất là Máy 1 với cv3=8 đơn vị thời
gian.
Lần phân công thứ hai: thì ta phải tìm máy nào có thời gian đã làm nhỏ nhất thì ta
nhận được kết quả là Máy 2 và Máy 3
Máy 2: thêm cv1+cv4  tổng cộng 8 đơn vị thời gian
Máy 3: thêm cv6  tổng cộng 6 đơn vị thời gian
Với cách phân công này ta thấy khi máy 1 làm xong cv3 thì máy 2 làm xong
cv5+cv1+cv4, máy 3 làm xong cv5+cv6
 Thời gian hoàn thành là 8 đơn vị thời gian
Chương trình cài đặt trên Pascal
uses crt;
const maxn=100;
fi='chia.inp';
fo='chia.out';
type m1=array[1 maxn] of longint;
var t,id:m1;
p:m1;
n,m,i:integer;
maxT:longint;
may:m1;
procedure readfile;
var i:integer;
f:text;
begin
assign(f,fi);

tim_may_min:=min;
end;
procedure writefile;
var g:text;
i,j:integer;
tong:longint;
begin
assign(g,fo);
rewrite(g);
writeln(g,maxT);
for j:=1 to m do
begin
tong:=0;
for i:=1 to n do {Viết ra số hiệu các công việc của máy j}
if p[i]=j then
begin
write(g,id[i],' ');
tong:=tong+t[i];
end;
writeln(g,' : ',tong); {lượng thời gian đã làm của máy j}
end;
close(g);
end;
procedure chia;
var i,j,lj:integer;
ok:boolean;
begin
fillchar(may,sizeof(may),0);
fillchar(p,sizeof(p),0);
i:=0;

may[j]:=may[j]+t[i];
p[i]:=j;
if may[j]>maxT then maxT:=may[j];
inc(i);
end;
end;
end;
begin
readfile;
sort;
chia;
writefile;
readln
end.
c. Phương pháp duyệt có đặt cận
Trong phương pháp này nếu chọn cận hợp lí với thời gian cho phép thì lời giải
thường đạt kết quả tương đối tối ưu. Vài lưu ý khi áp dụng:
- Thương sắp tăng hoặc giảm bộ dữ liệu theo một khóa giá trị nào đó trước khi
duyệt.
- Tìm cận là điều kiện cần để khi duyệt tránh đi vào các nhánh không dẫn tới đích.
Cận càng chặt chẽ càng nhanh chóng tới kết quả, nhưng cần phân tích kĩ để tránh
trường hợp bị mất nghiệm do đặt cận chặt chẽ quá mức hợp lí.
Ví dụ: Ta xét bài toán sau:
Cho N công việc, với mỗi công việc cho biết tiền công thu được khi thực hiện
công việc này, thời gian để hoàn thành, thời điểm cuối cùng phải kết thúc. Hãy xếp
lịch thực hiện sao cho thu được nhiều tiền công nhất.
Dữ liệu vào từ file văn bản XEPLICH.INP có cấu trúc:
- Dòng đầu là số nguyên dương N
- N dòng sau, dòng i+1 ghi 3 số tg, tdkt, gt tương ứng là thời gian cần thiết để hoàn
thành, thời điểm bắt buộc phải xong, giá trị tiền công của công việc i.

Tổng tiền k công việc+Giá trị tối đa các công việc còn lại>Tổng tiền của phương án
tốt nhất đã có.
Ta thấy rằng khi thử chọn công việc k thì có thể dẫn tới sự kiện hàng loạt công
việc khác bị loại vì việc hoàn thành công việc k sẽ đẩy lùi thời điểm có thể bắt đầu
thực hiện các công việc này dẫn đến đẩy lùi thời điểm hoàn thành chúng và do đó có
thể làm cho một số công việc không xong trước thời hạn kết thúc đã qui định cho nó.
Ngược lại nếu không chọn công việc k nữa thì lại tạo điều kiện có thể thực hiện
những công việc bị loại do chọn k.
Ngoài ra, một cận thứ hai là:
Thời điểm bắt đầu công việc k + thời gian làm công việc k
≤
Thời điểm kết thúc công
việc k.
Cài đặt chương trình sử dụng ngôn ngữ lập trình Pascal:
uses crt;
const max=1000;
fi='xeplich.inp';
fo='xeplich.out';
type pt=record
tg,tien,tdkt,ten:integer;
17
end;
var a,s,ls:array[1 max] of pt;
{a[i] chứa thời gian làm, tiền công, thời gian kết thúc, số hiệu công việc i,
s[i] chứa các công việc thử chọn, ls[i] chứa các công việc được chọn}
d:array[1 max] of integer;{Đánh dấu các công việc}
i,n,top,ltop:integer;
conlai:longint;{Tổng tiền các công việc còn lại}
tien,td,tong:integer;{Lần lượt là tổng tiền đã làm được, thời điểm cuối
của phương án đang tạo, tổng tiền của phương án tốt đã có}

end;
procedure select(k:integer);
var j:integer;
begin
tien:=tien+a[k].tien;{Thêm tiền công của công việc k}
d[k]:=k; {đánh dấu đã chọn làm công việc k}
conlai:=conlai-a[k].tien;{Tổng giá trị các công việc còn lại}
inc(top);
s[top].tg:=td;
td:=td+a[k].tg; {Tính thời điểm làm xong công việc k}
s[top].ten:=a[k].ten;
s[top].tdkt:=td;
s[top].tien:=a[k].tien;
for j:=1 to n do {Điều kiện để loại công việc j do chọn công việc k}
if (d[j]=0)and(a[j].tdkt<td+a[j].tg) then
begin
d[j]:=k;
conlai:=conlai-a[j].tien;
end;
18
end;
procedure remove(k:integer);{Không chọn công việc k nữa}
var j:integer;
begin
for j:=1 to n do
if d[j]=k then
begin
d[j]:=0;
conlai:=conlai+a[j].tien;
end;

writeln(f,ls[k].ten,' ',ls[k].tg,' ',ls[k].tdkt,' ',ls[k].tien);
close(f);
end;
begin
fillchar(d,sizeof(d),0);
td:=0;
readfile;
sort;
tong:=-maxint;
duyet;
writefile;
readln
end.
19
d. Ph¬ng ph¸p quy ho¹ch ®éng
Có những bài toán mà quyết định ở bước thứ i phụ thuộc vào quyết định ở các
bước trước đó. Nếu ta xác định được hệ thức diễn đạt mối tương quan của quyết đinh
ở bước thứ i với quyết định ở bước trước đó thì ta có thể triển khai chương trình theo
hệ thức đã tìm được.
Khi đó việc giải các bài toán có kích thước lớn sẽ được chuyển về việc giải các bài
toán cùng kiểu có kích thước nhỏ hơn.Các thuật toán này thường được thể hiện bằng
các chương trình con đệ quy.Tuy nhiên, với kỹ thuật chia để trị thì nhiều bài toán con
phải tính lại nhiều lần.
Vậy ý tưởng cơ bản của quy hoạch động đó là: Tránh tính toán lại các bài toán con
nhiều lần, mà lưu giữ kết quả đã tìm kiếm được vào một bảng làm giá trị giả thiết cho
việc tìm kết quả của trường hợp sau. Chúng ta sẽ lấp đầy dần các giá trị của bảng này
bởi các kết quả của những trường hợp trước đã được giải. Kết quả cuối cùng chính là
kết quả của bài toán cần giải.Cụ thể như sau:
Phương pháp quy hoạch động cùng nguyên lý tối ưu được nhà toán học Mỹ
R.Bellman đề xuất vào những năm 50 của thế kỷ 20. Phương pháp này đã được áp

Hãy tìm cách xóa đi một số ít nhất số hạng để dãy còn lại là dãy đơn điệu hay nói
cách khác hãy chọn một số nhiều nhất các số sao cho dãy B gồm các số hạng đó theo
trình tự xuất hiện trong dãy A là đơn điệu.
Quá trình chọn dãy B được điều khiển qua N giai đoạn để đạt được mục tiêu là
số lượng số hạng của dãy B là nhiều nhất, điều khiển ở giai đoạn i thể hiện việc chọn
hay không chọn dãy Ai vào dãy B.
Giả sử dãy đã cho là 1 8 10 2 4 6 7. Nếu ta chọn lần lượt 1, 8, 10 thì chỉ chọn
được 3 số hạng nhưng nếu bỏ qua 8 và 10 thì ta chọn được 5 số hạng 1, 2, 4, 6, 7.
Khi giải một số bài toán bằng cách "chia để trị", chuyển việc giải bài toán kích
thước lớn về việc giải nhiều bài toán cùng kiểu có kích thước nhỏ hơn thì các thuật
toán này thường được thể hiện bằng các chương trình con đệ quy. Khi đó, trên thực tế,
nhiều kết quả trung gian phải được tính nhiều lần.
Nói các khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên
lý chia để trị đến cao độ.
Trong một số trường hợp, khi giải một bài toán A, trước hết ta tìm họ bài toán
A(p) phụ thuộc tham số p (có thể là một véc tơ) mà A(p
0
)=A với p
0
là trạng thái ban
đầu của bài toán A. Sau đó tìm cách giải họ bài toán A(p) với tham số p bằng cách áp
21
dụng nguyên lý tối ưu của Bellman. Cuối cùng cho p=p0 sẽ nhận được kết quả của
bài toán A ban đầu.
Các thuật ngữ dùng trong quy hoạch động:
Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy hoạch động.
Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn gọi là
công thức truy hồi của quy hoạch động. Tập các bài toán có ngay lời giải để từ đó giải
quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động. Không gian lưu trữ lời giải
các bài toán con để tìm cách phối hợp chúng gọi là bảng phương án của quy hoạch

- Dòng đầu ghi số N (0<N
≤
1000)
- Dòng thứ i trong N dòng tiếp theo ghi ba số d
i
, c
i
, p
i
cách nhau bởi dấu trống, i=1,
2, …, N
Dữ liệu ra ghi vào file MAYTINH.OUT có cấu trúc:
- Dòng đầu tiên ghi hai số nguyên dương theo thứ tự là số lượng khách hàng nhận
được phục vụ và tổng tiền thu được.
- Dòng tiếp theo ghi chỉ số của khách hàng được phục vụ.
Test:
MAYTINH.INP MAYTINH.OUT
22
3
150 500 150
1 200 100
400 800 80
2 180
3 2
MAYTINH.INP MAYTINH.OUT
4
400 821 800
200 513 500
100 325 200
600 900 600

nh:array[0 1000] of longint;
t:array[1 1000] of integer;
n,i:integer;
procedure readfile;
var i:integer;
f:text;
23
begin
assign(f,fi);
reset(f);
a[0].d:=0;a[0].c:=0;a[0].p:=0;
readln(f,n);
for i:=1 to n do
with a[i] do
readln(f,d,c,p);
for i:=1 to n do a[i].tt:=i;
for i:=1 to n do write(a[i].d,' ');
end;
procedure QuickSort;
procedure Sort(l,r:integer);
var
i,j:integer;
x:longint;
y:khach;
begin
i:=l;j:=r;x:=a[(l+r) div 2].d;
repeat
while a[i].d<x do inc(i);
while x<a[j].d do dec(j);
if i<=j then

end;
procedure writefile;
var max:longint;
i,li,sl:integer;
f:text;
begin
24
assign(f,fo);
rewrite(f);
max:=-maxint;
for i:=1 to n do
if max<nh[i] then
begin
max:=nh[i];
li:=i;
end;
sl:=0;
i:=li;
repeat
inc(sl);
i:=t[i];
until i=0;
writeln(f,sl,' ',max:0);
i:=li;
repeat
write(f,a[i].tt,' ');
i:=t[i];
until i=0;
close(f);
end;