BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC LẠC HỒNG
***
VŨ ĐÌNH TRUNG
SONG SONG HÓA BÀI TOÁN JSP TRÊN MỘT SỐ MÔI
TRƯỜNG TÍNH TOÁN SONG SONG VÀ PHÂN TÁN
Chuyên ngành: Công nghệ thông tin
Mã ngành: 60 48 02 01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. TRẦN VĂN LĂNG Đồng Nai – Năm 2012
-i-
LỜI CAM
ĐOANTôi xin cam đoan luận văn thạc sĩ công nghệ thông tin “Song song hóa bài toán
LỜI CẢM ƠN
Lời đầu tiên tôi xin chân thành cảm ơn đến PGS. TS. Trần Văn Lăng đã tận
tình giúp đỡ tôi trong suốt thời gian học tập vừa qua, và hướng dẫn tôi hoàn thành
đề tài này
Tôi chân thành cảm ơn các thầy cô Khoa Công nghệ thông tin, nơi tôi công
tác và nghiên cứu đã tạo điều kiện và hỗ trợ tôi trong suốt thời gian qua.
Tôi cũng xin chân thành cảm ơn người thân, bạn bè đã giúp đỡ và động viên
tôi trong suốt thời gian học tập cũng như trong thời gian thực hiện luận văn.
Chân thành cảm ơn !
Biên Hòa, ngày 31 tháng 8 năm 2012
Vũ Đình Trung
-iii-
TÓM TẮT
Lập lịch công việc là bài toán đã ra đời từ rất lâu, nhưng đến nay vẫn chưa có
một phương pháp nào giải quyết bài toán lập lịch công việc một cách chính xác với
thời gian ngắn. Những nghiên cứu gần đây theo xu hướng nhắm vào mục đích làm
giảm đến mức thấp nhất thời gian hoàn thành bài toán, ưu điểm lớn của những
hướng đi này là kết quả đạt được với thời gian thấp nhưng lịch trình tìm được chỉ
đạt mức gần đúng trong khả năng chấp nhận được.
Từ mục đích và hạn chế đó tác giả tiến hành nghiên cứu một thuật toán có
thể cải thiện được về mặt thời gian mà kết quả lịch trình cho ra vẫn chính xác.
Qua nhiều nghiên cứu của những công trình trước, thì nhánh cận được xác
định là thuật toán tốt nhất trong các phương pháp tìm kiếm chính xác. Nhưng vấn
4. Đối tượng nghiên cứu 4
5. Nội dung nghiên cứu 4
6. Phương pháp nghiên cứu 5
CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH CÔNG VIỆC 6
1.1. Định nghĩa bài toán lập lịch 6
1.1.1. Mô tả bài toán 6
1.1.2. Dữ liệu bài toán 6
1.1.3. Các loại lịch trình 6
1.2. Tình hình nghiên cứu thuật toán tuần tự để giải quyết bài toán lập lịch công việc
9
1.2.1. Tình hình nghiên cứu trên thế giới 9
1.2.1.1. Phương pháp chính xác 11
1.2.1.2. Phương pháp gần đúng 12
1.2.2. Tình hình nghiên cứu trong nước 25
1.2.3. Một số công trình biêu biểu 26
-iv-
1.3. Tình hình nghiên cứu thuật toán song song để giải quyết bài toán lập lịch công
việc 43
1.3.1. Tình hình nghiên cứu ngoài nước 43
1.3.2. Tình hình nghiên cứu trong nước 43
1.3.3. Một số công trình tiêu biểu 44
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT 51
2.1. Tổng quan về tính toán song song 51
2.1.1. Sự cần thiết của tính toán song song và phân tán 51
2.1.2. Mô hình máy tính song song 52
2.1.2.1. Phép phân loại Flynn 52
2.1.2.2. Chia sẻ bộ nhớ cục bộ 55
2.1.3. Mô hình máy tính phân tán 56
2.1.4. Kỹ thuật lập trình song song 56
2.1.4.1. Những mô hình lập trình song song 56
4.1. Kết quả thử nghiệm trên thuật toán nhánh cận song song giải quyết bài toán lập
lịch trên nhiều máy tính 97
4.2. Kết quả thử nghiệm thuật toán nhánh cận song song giải quyết bài toán lập lịch
công việc trên môi trường CPU – GPU 99.
KẾT LUẬN 102
TÀI LIỆU THAM KHẢO
-v-
DANH MỤC TỪ VIẾT TẮT CA Clustering agorithm
d Due date
f Fitness
GCA Genetic clustering algorithm
GPU Graphics processing unit
JSP Job shop problem
MIMD Multiple instruction stream, multiple data stream
MPI Message passing interface
MISD Multiple instruction stream, single data stream
L Lateness
LB Lower bound
LIS Language independent specifications
O Operation
PU Processor Unit
r Realease date
SISD Single instruction stream, single data stream
SIMD Single instruction stream, multiple data stream
SPMD Single program multiple data
8
Biểu đồ 1.4: Lịch trình chủ động sau khi thay đổi trình tự công đoạn 9
Biểu đồ 1.5: Biểu đồ Gantt mô tả trình tự thực hiện công việc 1 22
Biểu đồ 1.6: Biểu đồ Gantt mô tả trình tự thực hiện công việc 2 31
Biểu đồ 1.7: Biểu đồ Gantt mô tả trình tự thực hiện công việc 3 34
Biểu đồ 1.8: Biểu đồ Gantt mô tả trình tự thực hiện công việc 4 35
Biều đồ 1.9: Biểu đồ Gantt mô tả trình tự thực hiện công việc 5 36
Biều đồ 1.10: Biểu đồ Gantt mô tả trình tự thực hiện công việc 6 37
Biều đồ 1.11: Biểu đồ Gantt mô tả trình tự thực hiện công việc 7 38
-viii-
DANH MỤC HÌNH Hình 2.1: Mô hình máy tính SISD 52
Hình 2.2: Mô hình máy tính SIMD 53
Hình 2.3: Mô hình máy MIMD 54
Hình 2.4: Máy tính chia sẻ bộ nhớ 55
Hình 2.5: Máy tính bộ nhớ phân tán 56
Hình 2.6: Mô hình máy tính phân tán 56
Hình 2.7: Mô hình phân chia chức năng 58
Hình 3.1: Nhánh mở rộng từ nút (2, 2) 87
Hình 3.2: Mở rộng nhánh từ (3, 1), LB>minLB 88
Hình 3.3: Mở rộng nhánh từ (3,1), LB <minLB 89
Hình 4.1: Đồ thị biểu diễn thời gian xử lý các thuật toán 1 98
Hình 4.2: Đồ thị biểu diễn thời gian xử lý các thuật toán 2 100
mình, được tạo nên từ cách viết chương trình tuần tự sang cách viết chương trình
song song. Các thuật toán tuần tự cũng được chuyển biến thành thuật toán song
song. Khi phần cứng và phần mềm đã tương thích với nhau thì hiệu suất thực hiện
2
công việc sẽ tăng lên đáng kể và nhu cầu khối lượng công việc cần xử lý cũng như
thời gian hoàn thành công việc sẽ được đáp ứng.
Với phương hướng trên, thì việc xây dựng hoặc cải tiến các thuật toán để tạo
nên thuật toán song song là cần thiết. Cụ thể trong đề tài này tác giả tiến hành
nghiên cứu để tạo nên một thuật toán song song áp dụng giải quyết bài toán “Lập
lịch trình công việc (JSP – Job Shop Problem)”. Việc lập lịch được hình thành từ
khi con người bắt đầu có sự phân công công việc trong xã hội và vẫn tiếp tục tồn
tại, phát triển cùng sự tiến bộ của khoa học kỹ thuật. Một lịch trình tốt sẽ giúp cho
thời gian hoàn thành công việc ngắn lại góp phần tiết kiệm thời gian. Vì thế trải qua
nhiều thập kỷ người ta không ngừng tìm hiểu và phát triển các phương pháp lập
lịch để có được một lời giải tốt nhất.
Vấn đề lập lịch trình công việc có thể áp dụng cho các mục đích khác nhau.
Ví dụ về lập lịch công tác của nhân viên trong một bộ phận của công ty. Với yêu
cầu này ta có thể mô tả sơ bộ như sau: bộ phận của công ty bao gồm một tập hợp
các nhân viên và một tập hợp các công việc phải thực hiện vào những thời gian xác
định. Mỗi nhân viên có khả năng thực hiện một số công việc và có đặc điểm sở
thích riêng của mình về công việc cũng như thời gian làm việc. Lập lịch là gán việc
cho các nhân viên sao cho đảm bảo các công việc phải được hoàn thành đúng kế
hoạch. Với ví dụ điển hình như trên thì ta có thể áp dụng để lập lịch với các kiểu bài
toán tương tự như: lập thời khóa biểu học cho sinh viên, phân ca trực cho y tá trong
bệnh viện, phân giờ dạy cho giáo viên trong các trung tâm đào tạo, phân công ca lái
xe cho các nhân viên công ty vận tải, …
Với nhiều ứng dụng như vậy, bởi lẽ đó thì việc nghiên cứu để đưa ra một
thuật toán song song có thể thống kê một lịch trình để thực hiện các công việc hoàn
thành trong thời gian tối ưu nhất là cần thiết.
pháp chính xác là chi phí thời gian tìm kiếm để đưa ra lời giải thấp. Một số thuật
toán mạnh mẽ gần đây tiếp cận bằng phương pháp gần đúng bao gồm: “Taboo
Search”, “Genetic Algorithms”, “Simulated Annearling”, …
Từ hai phương pháp tiếp cận trên, để có thể tìm được một lời giải tối ưu nhất
và thời gian thực hiện nhanh nhất thì tác giả đã chọn thuật toán nhánh cận để tiến
hành giải quyết bài toán lập lịch trình công việc. Với thuật toán nhánh cận thì một
đáp án tối ưu nhất luôn được tìm ra, nhưng vấn đề vấp phải là chi phí tìm kiếm lớn.
Trong điều kiện áp dụng triển khai thuật toán trên môi trường tính toán song song
thì sẽ góp phần giải quyết được nhược điểm về chi phí tìm kiếm của thuật toán. Do
4
đó việc cải tiến thuật toán nhánh cận từ môi trường máy đơn thành thuật toán có thể
xử lý song song trên môi trường tính toán song song là phù hợp với yêu cầu đặt ra.
3. Mục tiêu
Nghiên cứu thuật toán song song để giải quyết bài toán lập kế hoạch thông
qua việc giải quyết bài toán JSP. Từ đó có được sự đánh giá và so sánh với thuật
toán tuần tự.
Bên cạnh đó, cũng đề ra mục tiêu hiện thực thuật toán trên môi trường mạng
các máy tính song song (Networked Parallel Computer) và môi trường khai thác
đồng thời CPU lẫn GPU.
4. Đối tượng nghiên cứu
Với việc áp dụng thuật toán nhánh cận để giải quyết bài toán lập lịch thì một
lời giải tối ưu sẽ được tìm ra. Nhưng chi phí để tìm ra lời giải là quá lớn, các xử lý
và bộ nhớ dùng để lưu trữ đều tập trung tại một máy dẫn đến tình trạng tràn bộ nhớ,
do đó vấn đề cần phải nghiên cứu ở đây là cách thức hoạt động của thuật toán nhánh
cận, từ đó tiến hành xây dựng, phân chia các xử lý về các máy con đồng thời tận
dụng bộ nhớ của các máy con đó, nhằm tiến tới mục đích cuối cùng là tạo ra một
thuật toán song song cho vấn đề lập lịch trình công việc.
5. Nội dung nghiên cứu
▪ Nghiên cứu các loại lịch trình
1.1. Định nghĩa bài toán lập lịch
1.1.1. Mô tả bài toán
Giả sử có tập m máy M
j
(j=1,…,m) và tập n công việc J
i
(i=1,…,n). Lịch biểu
cho mỗi công việc là sự phân công xử lý công việc đó trên một hay nhiều máy. Bài
toán lập lịch có một số ràng buộc sau:
▪ Một máy chỉ có thể thực hiện một công việc tại một thời điểm
▪ Một công việc có nhiều nhất là m công đoạn thực hiện
▪ Một công việc khi đã bắt đầu xử lý thì nó không được gián đoạn
▪ Mỗi công việc được xử lý trên các máy theo một trình tự nhất định
▪ Trình tự công đoạn trên các máy chưa được xác định và cần phải xác
định trình tự này để có được thời gian hoàn thành là nhỏ nhất.
1.1.2. Dữ liệu bài toán
Công việc J
i
phải trải qua n
i
công đoạn O
i1
, O
i2
, O
i3
, …, O
in,
, tương ứng với
mỗi công đoạn O
xử lý hoặc vi phạm những ràng buộc [9] .
Ví dụ: một lịch trình không phải bán chủ động trong trường hợp biểu diễn trên biểu
đồ Gantt như biểu đồ 1.1:
7 Biểu đồ 1.1: Lịch trình không phải là bán chủ động
Từ biểu đồ Gantt trên, có thể xác định đây không phải là lịch trình bán chủ
động. Vì có thể thực hiện công đoạn O
12
và O
13
sớm hơn mà trình tự thực hiện vẫn
không đổi. Tiến hành thực hiện công công đoạn O
12
và O
13
sớm hơn để được một
lịch trình bán chủ động. Khi đó biểu đồ gantt thu được như biểu đồ 1.2:
Biểu đồ 1.2: Lịch trình bán chủ động
Lịch trình chủ động (active): một lịch trình được gọi là chủ động nếu không
thể xếp lại lịch cho các công việc thực hiện sớm hơn mà không vi phạm các ràng
buộc. Biểu đồ 1.2 trên là lịch trình bán chủ động, khi đó sẽ không thể thực một bất
cứ một công đoạn nào khác sớm hơn mà không làm thay đổi trình tự thực hiện của
các công đoạn. Tuy nhiên, từ lịch trình bán chủ động nếu thay đổi trình tự thực hiện
các công đoạn tại một máy bất kỳ thì có thể được một lịch trình chủ động. Như vậy
8
có thể kết luận, lịch trình bán chủ động không phải là một lịch trình tối ưu. Lịch
có thể được tìm thấy trong công trình nghiên cứu của Akers và Friedman. Tiếp sau
đó là công trình nghiên cứu của Bowman (1959) và Wagner (1959), khi đó thì các
công việc chỉ có thể được xử lý trên 3 máy tính hoặc ít hơn. Năm 1963 là năm đánh
dấu cột mốc lịch sử quan trọng về bài toán lập lịch JSP, khi đó Fisher và Thompson
đã giới thiệu công trình nghiên cứu xử lý 10 công việc trên 10 máy tính khác nhau.
Từ đó các nỗ lực thách thức về bài toán lập lịch JSP được tạo ra, thực hiện bởi
Brooks và White (1965), Greenberg (1968) dùng phương pháp quy hoạch số
nguyên (integer programming). Sau đó là phương pháp nhân tử Lagrange của Balas
(1969), Charlton và Death (1970), Florian (1971), Ashour và Hiremath (1973), và
Fisher (1973).
Một thuật toán của McMahon và Florian đề xuất ra vào năm 1975 là lịch
trình đầu tiên chính xác nhất. Phương pháp của tác giả kết hợp các giới hạn của vấn
đề lập lịch trên một máy tính bằng cách sử dụng hàm mục tiêu để giảm thiểu thời
gian trễ và liệt kê các lịch trình chủ động (active schedule).
Cũng vào thời điểm đó, phương pháp giải quyết bài toán lập lịch JSP sử
dụng hàm ước lượng heuristic dựa trên các luật ưu tiên được nghiên cứu bởi Gere
(1966), Panwalker và Iskander (1977), Haupt (1989). Xa hơn nữa là một số thuật
10
toán mạnh mẽ được nghiên cứu với các phương pháp tiếp cận tối ưu, năm 1985
Barker và McMahon công bố công trình nghiên với phương pháp giải quyết bài
toán lập lịch bằng cách sử dụng cấu trúc lân cận dựa vào thuật toán tìm kiếm địa
phương (local search).
Năm 1982, bài toán lập lịch JSP xuất hiện tại Pháp và được xem là dạng bài
toán đặc biệt khó về vấn đề tối ưu tổ hợp. Từ các ứng dụng thực tế thì vấn đề này đã
được nghiên cứu bởi nhiều tác giả với những lịch trình khác nhau. [11]
Sau đây là các phương pháp áp dụng để giải bài toán lập lịch JSP:
Hình 1.1: Các phương pháp giải bài toán lập lịch công việc
max
là chiều
dài lớn nhất đi từ nút nguồn đến nút đích.
Hiệu quả của lời giải khi sử dụng thuật toán nhánh cận để giải quyết vẫn phụ
thuộc vào hai yếu tố là phân nhánh và đánh giá cận chính xác hay không. Do đó
12
nhiều loại thủ tục khác nhau được đưa ra phát triển để đáp ứng yêu cầu trên: xác
định cận dựa vào phương pháp lagrange nới lỏng (lagrange relaxation), phương
pháp đối ngẫu thay thế (surrogate duality) và các lịch trình tối ưu của một vấn đề
con bao gồm hai hoặc ba công việc trên nhiều máy tính.
Thủ tục nổi bật nhất để xác định cận được đề xuất bởi Carlier (1982) và Pots
(1980). Thủ tục được hình thành bắt nguồn từ một lịch trình chính xác để lập lịch
trên máy đơn dựa vào thời điểm bắt đầu và thời điểm kết thúc để lập một kế hoạch
tối ưu cho vấn đề lập lịch công việc. Về sau thủ tục này được cải tiến bởi Balas,
Lenstra và Vazacopoulous (1995) bằng cách giảm thiểu sự chậm trễ giữa các cặp
công đoạn với nhau. Sau đó nhiều cách thức suy luận khác nhau được bổ sung vào
với cùng mục đích để giới hạn lại không gian tìm kiếm. Florian (1971) đề xuất một
thuật toán nhánh cận trong đó việc xác định tập ứng cử viên có thể phân nhánh như
sau: tại một thời điểm nhất định tập các công đoạn sẵn sàng mà có các công đoạn
trước nó chưa được lên lịch thì đều được xem là ứng viên có thể phân nhánh, và
nhiều phương pháp khác được đưa ra của các tả giả barker và McMaHon (1985),
Brucker (1992, 1994), Carlier và Pinson (1989, 1990, 1994) thuật toán dựa trên các
cặp cung rời xác định nối với nhau hay không trên hai cây con. Năm 1996, Martin
đã đề xuất phương pháp tiếp cận hướng thời gian với một kỹ thuật mạnh mẽ được
gọi là shaving. Trong các phương pháp được đề xuất trước đó thì phương pháp của
Martin được đánh giá là tốt nhất nhưng vấn đề gặp phải ở phương pháp này là thời
gian tính toán quá lớn. [11]
1.2.1.2. Phương pháp gần đúng
Tìm kiếm địa phương (local search)
phương trong miền lân cận N(s) của lời giải s (nghĩa là không có lời giải nào tốt hơn
lời giải hiện tại có được trong miền lân cận này). Tuy nhiên giá trị này có thể khác
đáng kể so với giả trị cực tiểu toàn cục. [7]
Thuật toán mô phỏng luyện kim (simulated annealing)
Dựa trên cơ sở phương pháp tìm kiếm địa phương, thuật toán mô phỏng
luyện kim là phương pháp tìm kiếm tránh rơi vào cực tiểu địa phương. Mô phỏng
luyện kim là phương pháp ngẫu nhiên vì:
▪ s’ được lựa chọn ngẫu nhiên từ tập N(s)
▪ Tại bước lặp thứ i, lời giải s’ được chấp nhận với xác suất:
min{1, exp(-
′
()
)}
14
Xác suất này được hiểu như sau : c(s’) ≤ c(s) thì lời giải s được thay thế bởi
lời giải s’ với xác suất bằng 1. Ngược lại c(s’) > c(s) thì lời giải được thay thế bằng
lời giải s’ với một xác suất. Xác suất này sẽ giảm dần khi i tăng. Như vậy thuật toán
sẽ thoát khỏi cực tiểu địa phương nhưng xác suất để thực hiện việc này sẽ giảm dần
sau một số lớn bước lặp. Trong thuật toán, ký hiệu random[0. 1] tượng trưng cho
một hàm số tạo một giá trị ngẫu nhiên trong khoảng 0 đến 1. Ngoài ra, dãy {c
i
}
được tạo ra bởi hàm số g, nghĩa là c
i+1
=g(c
i
thể xảy ra và điều này dẫn đến mất nhiều thời gian tính toán trên một phần nhỏ của
không gian lời giải. [7]
Copyright: Tài liệu đại học ©