Đại Học Quốc Gia Tp. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA

-------------------

HỒ DOÃN QUỐC

ĐIỀU ĐỘ TỐI ƯU JOB SHOP
VỚI THỜI GIAN GIA CƠNG NGẪU NHIÊN
Chun ngành: Kỹ Thuật Hệ Thống Cơng Nghiệp

LUẬN VĂN THẠC SĨ

Tp.Hồ Chí Minh, tháng 07 năm 2010
 


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
Cán bộ hướng dẫn khoa học: ....................................................................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 1: ...........................................................................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 2: ...........................................................................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Luận văn thạc sĩ được bảo vệ tại Trường Đại Học Bách Khoa, ĐHQG Tp.HCM ngày
. . . . . . tháng . . . . . . năm . . . . . .
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. ...............................................................................
2. ...............................................................................

3. ...............................................................................
4. ...............................................................................
5. ...............................................................................
Xác nhận của Chủ Tịch Hội Đồng đánh giá LV và Bộ môn quản lý chuyên ngành sau
khi luận văn đã được sửa chữa (nếu có)
Chủ tịch Hội đồng đánh giá LV

Bộ môn quản lý chuyên ngành


ĐẠI HỌC QC GIA TP.HCM

TRƯỜNG ĐẠI HỌC BÁCH KHOA
----------------

CỘNG HỊA XÃ HỘI CHỦ NGHĨA VIỆT NAM

Độc Lập - Tự Do - Hạnh Phúc
---oOo--Tp. HCM, ngày . . . . . tháng . . . . . năm 2010

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên:

HỒ DOÃN QUỐC

Phái : Nam

Ngày, tháng, năm sinh : 23/10/1973

Nơi sinh : Quảng Nam


Chuyên ngành : Kỹ Thuật Hệ Thống Công Nghiệp

MSHV: 02708266

1- TÊN ĐỀ TÀI:
ĐIỀU ĐỘ TỐI ƯU JOB-SHOP VỚI THỜI GIAN GIA CÔNG NGẪU NHIÊN
2- NHIỆM VỤ LUẬN VĂN:
Nghiên cứu giải thuật di truyền áp dụng cho các bài toán job-shop.
Nghiên cứu kỹ thuật mơ phỏng cho bài tốn job-shop.
Nghiên cứu kỹ thuật tích hợp giữa giải thuật di truyền và phương pháp mô phỏng.
Áp dụng kết quả nghiên cứu vào bài toán điều độ job-shop
Xây dựng phần mềm hổ trợ giải bài tốn điều độ job-shop có thời gian gia cơng ngẫu nhiên.
Kiểm định và đánh giá giải thuật.
Kết luận và kiến nghị.
3- NGÀY GIAO NHIỆM VỤ :

23/01/2010

4- NGÀY HOÀN THÀNH NHIỆM VỤ : 02/07/2010
5- CÁN BỘ HƯỚNG DẪN:

PGS.TS. Hồ Thanh Phong.

Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua.
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

CHỦ NHIỆM BỘ MÔN
QUẢN LÝ CHUYÊN NGÀNH

(Họ tên và chữ ký)

PGS.TS. HỒ THANH PHONG

GVC.ThS. NGUYỄN NHƯ PHONG


2

LỜI CẢM ƠN
Tơi xin dâng tặng cơng trình nghiên cứu khoa học này như là một đóa hoa gửi
đến những người Thầy đã truyền đạt kiến thức, đào tạo tôi trong suốt thời gian học tập
tại trường.
Tôi xin chân thành cảm ơn PGS.TS Hồ Thanh Phong, là người Thầy đã hết lịng
hướng dẫn tơi hồn thành luận văn này. Được gần Thầy và được sự huấn luyện của
Thầy là niềm may mắn và hạnh phúc cho tôi trong khoảng thời gian vừa qua. Phương
pháp đặt vấn đề và kỹ thuật nhìn nhận vấn đề dưới nhiều góc độ khác nhau là điều tơi
học được từ người Thầy rất kính trọng này.
Tôi xin gửi lời cảm ơn đến các bạn của các khóa trước, là các bạn đã để lại kỹ
thuật viết chương trình trong các cơng trình nghiên cứu của mình. Phần mã nguồn trong
luận văn này là sự kế thừa từ các cơng trình của các bạn.
Tơi xin cảm ơn các bạn trong cùng khóa, hai năm học chung với các bạn thật là
vui.
Cuối cùng tôi xin gửi lời tri ân đến những thành viên trong gia đình đã tạo mọi
điều kiện cho tơi hồn thành luận văn này. Đặc biệt là người vợ và hai con nhỏ đã hổ
trợ và hy sinh rất nhiều cho tơi.
Tp Hồ Chí Minh, tháng 7 năm 2010
Hồ Doãn Quốc.



3

Abstract:
Điều độ tối ưu trong môi trường ngẫu nhiên đang được quan tâm nghiên cứu trong
những năm gần đây. Luận văn này đề cập đến bài toán job-shop với thời gian gia công
ngẫu nhiên. Phương pháp mô phỏng được sử dụng để đưa ra kết quả trong môi trường
ngẫu nhiên. Một phương pháp tiếp cận kết hợp giải thuật di truyền và mơ hình mơ
phỏng đảm bảo lời giải đạt được tối ưu. Kỹ thuật kết hợp điều khiển tự động giữa các
phần mềm Visual Basic, Microsoft Excel, Arena được thực thi phương pháp tích hợp
trên. Khơng gian dị tìm lời giải cho bài toán job-shop được giảm bớt bằng kỹ thuật điều
độ tích cực tồn phần. Giải thuật di truyền được cải biên để sử dụng nhằm giảm thời
gian đạt được lời giải nhưng vẫn duy trì khả năng đạt được tối ưu của giải thuật. Giải
thuật di truyền cải biên với tham số tỷ lệ lai tạo và đột biến là toàn phần, một tham số
mới của giải thuật là tỷ lệ nhảy gen để duy trì tính đa dạng của quần thể và cơ chế duy
trì những cá thể tốt cũng được áp dụng trong giải thuật. Kỹ thuật mới để khắc phục việc
hội tụ sớm của giải thuật được đề xuất trong luận văn. Mơ hình mô phỏng được thực
hiện kiểm định với cả hai dạng là điều độ với máy không dừng và điều độ theo kế
hoạch định trước. Một phần mềm được xây dựng cho bài tốn job-shop có thời gian gia
cơng ngẫu nhiên với hàm mục tiêu là thời gian hoàn thành sớm nhất được xây dựng.
Việc kiểm định phần mềm trên được thực hiện trên các bài toán mẫu và so sánh với các
giải thuật khác trong môi trường job-shop.
Keywork: Simulation Optimization, Job Shop Scheduling Problem, Genetic Algorithm,
Arena.


4
MỤC LỤC
Chương 1: GIỚI THIỆU .............................................................................................................7
U


1.1.

Cơ sở lý do hình thành đề tài ........................................................................................7

1.2.

Mục tiêu của đề tài........................................................................................................7

1.3.

Nội dung nghiên cứu.....................................................................................................8

1.4.

Phạm vi và Giới hạn của đề tài .....................................................................................8

1.5.

Tổng quan cấu trúc luận văn.........................................................................................8

Chương 2: CÁC NGHIÊN CỨU LIÊN QUAN........................................................................10
2.1.

Giải thuật di truyền cải biên đối với bài toán job-shop :.............................................10

2.2.

Tích hợp tối ưu và mơ phỏng .....................................................................................10

2.3.


Ứng dụng phương pháp tích hợp tối ưu và mơ phỏng . ..............................................12

Chương 3: CƠ SỞ LÝ THUYẾT..............................................................................................14
3.1.

Các lý thuyết cơ sở......................................................................................................14

3.2.

Khái niệm mơ phỏng tối uu. .......................................................................................17

Chương 4: XÂY DỰNG CƠNG CỤ TÍCH HỢP TỐI ƯU MƠ PHỎNG ................................20
4.1.

Khơng gian tìm kiến lời giải .......................................................................................20

4.2.

Giải thuật di truyền lai cho bài toán jobshop ..............................................................23

4.3.

Xây dựng mơ hình mơ phỏng bài tốn job shop.........................................................27

4.4.

Cơ chế tối ưu hóa mơ phỏng bằng giải thuật di truyền:..............................................30

4.5.


Cơ chế điều khiển mô phỏng tối ưu :..........................................................................30

4.6.

Phần mềm hổ trợ. ........................................................................................................32

Chương 5: THIẾT KẾ VÀ KIỂM ĐỊNH GIẢI THUẬT..........................................................34
5.1.

Các chỉ tiêu đánh giá và thiết kế cơ chế hoạt động giải thuật.....................................34

5.2.

Khái niệm truởng thành sớm và cơ chế chuyển hướng lời giải ..................................34

5.3.

Thiết kế thực nghiệm với các thông số: ......................................................................38

5.4.

So sánh giải thuật với các nghiên cứu khác:...............................................................39

5.5.

Kiểm định giá trị mơ hình trước khi tích hợp với mơ phỏng:.....................................41

5.6.


Ảnh hưởng của yếu tố ngẫu nhiên đối với các kết quả tất định..................................43

5.7.

Thực nghiệm công cụ tích hợp tối ưu và mơ phỏng: ..................................................44

5.8.

Đánh giá tổng thể ưu khuyết điểm của giải thuật: ......................................................50

Chương 6: KẾT LUẬN VÀ KIẾN NGHỊ ................................................................................54
6.1.

Kết luận.......................................................................................................................54

6.2.

Kiến nghị:....................................................................................................................54

Chương 7: Tài liệu tham khảo ..................................................................................................55


5

DANH MỤC HÌNH ẢNH
Hình 2-1: Sơ đồ giải thuật effective hybrid genetic algorithm ................................................. 11
Hình 3-1: Các bước cần thực hiện một bài tốn mơ phỏng ..................................................... 17
Hình 3-2: Sơ đồ q trình mơ phỏng được dẫn hướng bởi GA .............................................. 18
Hình 3-3: Sơ đồ kết hợp giữa kỹ thuật di truyền và mơ phỏng tối ưu ...................................... 19
Hình 4-1: Hình ảnh mơ tả chuỗi mã hóa bài tốn 3x3 job-shop. ............................................. 20

Hình 4-2 : Giới thiệu một lịch điều độ tích cực tồn phần...................................................... 22
Hình 4-3: Hình mơ tả vùng chứa lịch điều độ tối ưu bài toán job-shop................................... 23
Hình 4-4: Sơ đồ giải thuật JGGA (Jumping Gens Genetic Algorithm) .................................... 25
Hình 4-5: Sơ đồ giải thuật di truyền trong luận văn ................................................................ 26
Hình 4-6: Mơ hình tổng qt cho bài tốn điều độ jobshop..................................................... 27
Hình 4-7: Mơ hình ý niệm mơ hình mơ phỏng jobshop ........................................................... 27
Hình 4-8: Mơ hình mơ phỏng job-shop với lịch điều độ khơng dừng...................................... 28
Hình 4-9: Mơ hình mơ phỏng job- shop với lịch điều độ theo kế hoạch. ................................. 29
Hình 4-10: Sơ đồ tích hợp giải thuật di truyền và mơ phỏng trong luận văn........................... 30
Hình 4-11: Sơ đồ điều khiển tham số trong tối ưu mơ phỏng................................................... 31
Hình 4-12: Giao diện điều khển nhập tham số di truyền của phần mềm ................................. 32
Hình 4-13: Biển diễn quá trình kết quả qua các thế hệ của giải thuật..................................... 33
Hình 5-1: Hiện tượng trưởng thành sớm của giải thuật di truyền ........................................... 35
Hình 5-2: Mô tả sự thay đổi thế hệ bằng kỹ thuật hốn chuyển gen ........................................ 36
Hình 5-3: Đồ thị ảnh hưởng của yếu tố ngẫu nhiên lên giá trị tất định ................................... 44
Hình 5-4: Đồ thị mơ phỏng tối ưu, thời gian gia cơng xác định .............................................. 45
Hình 5-5: Đồ thị điều độ theo máy không dừng, thời gian gia cơng ngẫu nhiên ..................... 46
Hình 5-6: Đồ thị điều độ theo kế hoạch định trước, thời gian gia công ngẫu nhiên................ 46


6

DANH MỤC BẢNG BIỂU
Bảng 5-1: Kết quả thực nghiệm không áp dụng kỹ thuật thay đổi thế hệ................................. 37
Bảng 5-2: Kết quả thực nghiệm áp dụng kỹ thuật thay đổi thế hệ............................................ 37
Bảng 5-3: Bảng so sánh kết quả thực nghiệm lựa chọn biến đổi thế hệ................................... 37
Bảng 5-4: Bảng kết quả thực nghiệm giữa các bộ thông số ..................................................... 38
Bảng 5-5: Bảng thực nghiệm lựa chọn tham số cho giải thuật ................................................ 39
Bảng 5-6: Bảng kết quả so sánh với các giải thuật di truyền khác .......................................... 40
Bảng 5-7: Bảng kết quả so sánh với các giải thuật cơ sở hình thành luận văn ....................... 40

Bảng 5-8: Bảng tổng hợp kết quả của các bài toán mẫu.......................................................... 41
Bảng 5-9: Kết quả thực nghiệm kiểm định mơ hình điều độ theo máy không dừng ................ 42
Bảng 5-10: Kết quả thực nghiệm kiểm định mơ hình điều độ theo kế hoạch định trước ......... 42
Bảng 5-11: Bảng kết quả điều độ theo máy khơng dừng, bài tốn abz7, phân bố normal, độ
lệch 10%..................................................................................................................................... 47
Bảng 5-12: Bảng kết quả điều độ theo kế hoạch định trước, bài toán abz7, phân bố normal, độ
lệch 10%..................................................................................................................................... 48
Bảng 5-13: Bảng tổng kết kết quả đạt được sau thực nghiệm tích hợp mơ phỏng tối ưu......... 49
Bảng 5-14: Bảng đánh giá kết quả tích hợp mơ phỏng tối ưu của giải thuật........................... 50


7

Chương 1: GIỚI THIỆU
1.1. Cơ sở lý do hình thành đề tài
Điều độ sản xuất chiếm phần quan trọng trong hoạt động của nhà máy. Việc chủ
động kế hoạch sản xuất là mong muốn của các nhà quản lý. Trong mơi trường học
thuật, nhiều dạng bài tốn thuộc lĩnh vực điều độ đã được nghiên cứu để tối ưu lời giải.
Nhưng việc áp dụng những lời giải của những bài tốn mẫu điều độ vẫn cịn nhiều hạn
chế khi áp dụng vào thực tế sản xuất. Bởi vì, nhà sản xuất mong muốn nhiều mục tiêu
hơn so với các mục tiêu của bài toán mẫu và kết quả của hàm tối ưu trên lý thuyết sai
lệch nhiều do yếu tố ngẫu nhiên của môi trường sản xuất.
Trong 20 năm gần đây, kỹ thuật mơ phỏng và mơ hình hóa được quan tâm
nghiên cứu và phát triển. Việc áp dụng kỹ thuật mô phỏng làm thu hẹp khoảng cách
đáng kể giữa hai lĩnh vực nghiên cứu lý thuyết và ứng dụng thực tế. Ứng với từng bài
toán điều độ cụ thể, trong môi trường riêng biệt của từng nhà máy công cụ mô phỏng
được sử dụng nhằm thỏa mãn được các yêu cầu của nhà sản xuất. Xu hướng hiện nay
đang phát triển mô phỏng tối ưu nhằm để giải những bài tốn có hàm mục tiêu khơng
tường minh do các tham số luôn biến đổi.
Trong môi trường điều độ sản xuất, đối với tác động của yếu tố ngẫu nhiên, câu

hỏi được quan tâm của cả nhà ứng dụng và nhà nghiên cứu là liệu rằng có thể kết hợp
giữa phương pháp tối ưu và kỹ thuật mô phỏng cho các dạng bài toán điều độ. Phương
thức nào để đảm bảo là lời giải tối ưu hay là lời giải hợp phù hợp trong điều kiện hiện
tại. Việc áp dụng phương thức trên có phù hợp với điều kiện hiện nay không. Học viên
ngành kỹ thuật hệ thống công nghiệp may mắn là được đào tạo bài bản ở cả hai lĩnh vực
nghiên cứu tối ưu và mô phỏng, luận văn được hình thành nhằm giải đáp một phần của
câu hỏi trên. Tên đề tài luận văn là “Điều độ job-shop với thời gian gia công ngẫu
nhiên” .
1.2. Mục tiêu của đề tài
Xây dựng mơ hình tích hợp kỹ thuật tối ưu và mơ phỏng để giải bài tốn điều độ
job-shop tính đến yếu tố ngẫu nhiên của thời gian gia cơng.
Mơ hình được kiểm nghiệm thơng qua các bài toán mẫu chuẩn về job-shop trên
thế giới.


8

1.3. Nội dung nghiên cứu
Để có thể hồn thành được mục tiêu đề ra , những vấn đề sau có tính quyết định
• Nghiên cứu giải thuật di truyền áp dụng cho các bài tốn job-shop
• Nghiên cứu kỹ thuật mơ phỏng cho bài tốn job-shop.
• Nghiên cứu kỹ thuật tích hợp giữa giải thuật di truyền và phương pháp mơ
phỏng.
• Áp dụng kết quả nghiên cứu vào bài tốn điều độ job-shop.
• Xây dựng phần mềm hổ trợ giải bài tốn điều độ job-shop có thời gian gia
cơng ngẫu nhiên.
• Kiểm định giải thuật di truyền và đánh giá phần mềm hổ trợ.
• Áp dụng phần mềm vào bài tốn thực tế.
• Kết luận và kiến nghị.
1.4. Phạm vi và Giới hạn của đề tài

Với mục tiêu là xây dựng được một cơng cụ có khả năng áp dụng trong một
phạm vi nhất định, giới hạn của đề tài như sau:
¾ Thiết kế một kỹ thuật tích hợp giữa giải thuật di truyền và mơ phỏng bằng
Arena.
¾ Kỹ thuật tích hợp được áp dụng cho bài tốn điều độ job-shop có thời gian
gia cơng theo phân bố xác định.
¾ Hàm mục tiêu của lời giải là thời gian hoàn thành của cơng việc.
¾ Kiểm định phần mềm dựa trên các bài tốn mẫu job-shop.
¾ Các phần mềm được sử dụng là Visual Basic, Microsoft Excel, Arena.
¾ Đề tài chưa thực hiện việc áp dụng với bộ số liệu thực tế.
1.5. Tổng quan cấu trúc luận văn
Với các mục tiêu trên, cấu trúc tổng thể dự kiến của luận văn được phân bổ như
sau:
Chương 1 dành cho giới thiệu tổng quan về cơ sở, lý do hình thành đề tài, phạm
vi và giới hạn của đề tài, cấu trúc trình bày của luận của luận văn.
Chương 2 dành cho phần khảo sát các cơng trình nghiên cứu liên quan.


9

Chương 3 dành cho lý thuyết cơ sở được sử dụng trong đề tài luận văn và lựa
chọn giải thuật áp dụng cho mơ hình
Chương 4 sẽ trình bày cấu trúc, phương pháp tiếp cận để xây dựng phương pháp
tích hợp giữa tối ưu và mô phỏng.
Chương 5 kiểm định phần mềm được xây dựng trên các bài toán job shop mẫu,
nhằm làm cơ sở đánh giá cho mơ hình.
Chương 6 sẽ là phần kết luận và kiến nghị.


10


Chương 2:
CÁC NGHIÊN CỨU LIÊN QUAN
2.1. Giải thuật di truyền cải biên đối với bài toán job-shop :
Nhằm giảm bớt thời gian dị tìm của giải thuật di truyền, các nghiên cứu đã thực
hiện một số cơ chế thêm vào để điều khiển hoạt động cho giải thuật:
Tác giả Wang.L, [14] , năm 2002, đề xuất một hướng cải thiện tính năng dị tìm
trong vùng lân cận đối với các quần thể trong giải thuật GA. Phương pháp cải thiện
được áp dụng bằng cách dùng kỹ thuật SA (simulated annealing) thay cho bước đột
biến (mutation operator). Bằng việc kết hợp cả hai ưu điểm dị tìm tổng thể (global
search) của GA và thu hẹp khơng gian dị tìm của SA, giải thuật MGA tỏ ra vượt trội so
với các giải thuật đơn như GA, SA, TS, SB trong việc đạt đến lời giải tốt nhất ở các bài
toán mẫu. Trong giải thuật tác giả đề xuất điểm dừng lại của giải thuật là khi lời giải tốt
nhất của giải thuật không được cải thiện sau 30 thế hệ liên tiếp. Kích thước quần thể
trong giải thuật này là 20.
Tác giả Chaoyong, Y., năm 2008, [7] , đề xuất cải biên ở bước lai tạo trong giải
thuật. Giải thuật đề xuất phương hướng dị tìm, mỗi cá thể sẽ được thay thế cá thể mới
tốt hơn trong miền lân cận của cá thể đó. Tại bước lai tạo, thực hiện cơ chế dị tìm cá
thể tốt hơn so với bố mẹ. Cả hai phương pháp trên đều công bố là phù hợp với các bài
toán lớn với hàm mục tiêu là Cmax. Trong đó, giải thuật của tác giả Chaoyong đề xuất,
hầu hết đạt lời giải tối ưu đối với các bài toán mẫu. Thời gian giải bài toán nổi tiếng
mt10 là nhỏ hơn 20 giây và đạt cả 20 lần chạy thử. Sơ đồ của giải thuật được trình bày
ở trang sau.
2.2. Tích hợp tối ưu và mơ phỏng .
Các tác giả Jay April, Fred Glover, James P. Keely., [15], năm 2003, giới
thiệu tổng quát cách tiếp cận trong kỹ thuật mô phỏng tối ưu qua bài báo Practical
introduction to Simulation Optimization như phần huấn luyện tại hội nghị mô phỏng
mùa đơng. Qua đó, hướng tiếp cận chung gọi tích hợp mô phỏng và tối ưu là phương
pháp hộp đen (black-box). Vì khi đó, kết quả từ mơ phỏng sẽ chuyển về giải thuật dị
tìm và giải thuật sẽ đưa các thơng số đầu vào cho mơ hình mơ phỏng . Bài báo cũng đề

xuất, để giảm thời gian tính toán, một hướng tiếp cận khác là dữ liệu từ giải thuật sẽ


11

chuyển qua một siêu mơ hình (metamodel) để xác định là có cần thực hiện mơ phỏng
cho bộ dữ liệu này khơng.
Chuỗi gen

Tạo một điều độ tích cực

Dị tìm lân cận cho lịch điều độ

Khơng

Q trình
thực hiện
giải thuật
di truyền

Cải thiện được
makespan
Có

Tạo một điều độ tích cực tồn phần
Dị tìm lân cận cho lịch điều độ

Cải thiện được
makespan


Có

Khơng

Cập nhật lịch điều độ tích cực tồn phần và giá trị
makespan

Hình 2-1: Sơ đồ giải thuật effective hybrid genetic algorithm
(nguồn tham khảo [7])
Nguợc với hướng nhìn xem mơ phỏng là hộp đen, tác giả George, J. M.,
[16], năm 2007, đề xuất một phương pháp gọi là hộp trắng, theo đó lời để giảm thời
gian mô phỏng tối ưu bằng cách không tiếp tục thực hiện mô phỏng khi kết quả ban đầu
từ mô phỏng ảnh hưởng xấu đến hàm mục tiêu. Phương pháp áp dụng cho bài tốn jobshop vói hàm mục đơn mục tiêu Cmax hoặc Tardiness. Phương pháp thực hiện mô
phỏng được áp dụng là trở ngược (backward simulation) và các luật cắt xén (pruning
rules) trong nhiều năm nghiên cứu của tác giả. Kết quả áp dụng, thực hiện thử nghiệm
trên các bài toán mẫu với số máy nhỏ hơn 10. Trong khoảng thời gian nhỏ hơn 25 phút,
kết quả lời giải có độ lệch khoảng 7% so với lời giải tốt nhất được biết.


12

Tác giả Gholami, M., [10], năm 2008, đề xuất việc tích hợp mơ phỏng tối
ưu cho bài tốn job-shop phức hợp (flexible). Biến ngẫu nhiên là thời gian hỏng máy và
thời gian sửa chữa theo phân bố hàm mũ (exponential distribution), giải thuật xử dụng
là SGA (simple genetic algorithm). Hàm mục tiêu là cực tiểu kỳ vọng Cmax và cực tiểu
kỳ vọng trung bình tổng thời gian trễ. Bài báo kiểm định kết quả của các thông số ngẫu
nhiên tác động lên hàm mục tiêu.
2.3. Ứng dụng phương pháp tích hợp tối ưu và mô phỏng .
Về mặt ứng dụng tích hợp tối ưu và mơ phỏng trong mơi trường sản xuất,
các cơng trình đã được nghiên cứu như:

Tác giả Hồ Thanh Phong, [2], năm 1997, đã đề xuất một cơ chế tối ưu mô
phỏng dùng GAs để tối ưu thiết kế mặt bằng sản xuất theo ba mục tiêu: cực tiểu tổng
thời gian di chuyển (total travel time), cực đại tổng độ gần kề (total closeness ratings )
và cực đại độ linh hoạt (layout flexibility). Trong phương pháp này, GAs đã được sử
dụng để phát ra mặt bằng dựa trên sự quan sát bằng mô phỏng. Bằng cách xử lý tọa độ
của máy như các biến ra quyết định, khơng gian tìm kiếm được khảo sát mà khơng có
sự hạn chế nào thông qua lai ghép và đột biến. Con số các mặt bằng lựa chọn được xem
như không có giới hạn. Điều này làm thời gian mơ phỏng kéo dài nhưng sẽ đạt được kết
quả hội tụ toàn cục.
Tác giả Marcus Andersson., và các đồng sự, [17], năm 2008, đề xuất kết
hợp những ưu điểm của hai hướng tiếp cận trong điều độ là theo luật phân việc
(dispathching rules) và giải thuật tìm kiếm (metaheuristic search algorithms) vào mô
phỏng. Tác giả đề xuất giải thuật di truyền lai (hybrid GA) là sự kết hợp mã hóa để tìm
kích cở lô (batch) và luật phân việc cho một kế hoạch điều độ. Kỹ thuật tích hợp này áp
dụng vào điều độ thực tế cho một chuyền sản xuất trục động cơ nhà máy Volvo. Hàm
mục tiêu là tổng độ chặt chẽ (fitness) của các hàm tốc độ sản xuất (throughput rate), tồn
trữ (shortage), mức sản xuất (target level), khả năng dừng chuyền (stopped in advance)
và thời gian chuẩn bị (setup time).
Tác giả Yasmina H., và các đồng sự, [18], năm 2008, áp dụng kỹ thuật tích
hợp GA trong mơ phỏng để tìm chính sách bảo dưỡng tối ưu cho khu vực bảo trì xe lửa.
Cơ chế tối ưu là dùng cả hai phương pháp tiếp cân dùng GA là non-pareto và pareto
(NSGA-2) với phầm mềm mô phỏng Arena. Hàm mục tiêu là đa mục tiêu, cực đại


13

lượng xe (high vehice number), cực tiểu thời gian lưu trữ (lower immobilization
duration) và cực tiểu tỷ lệ vận hành (lower occupation rate). Bài báo kết luận là tiếp cận
theo hướng pareto cho ra kết quả đa dạng hơn nhưng thời gian giải dài hơn so với
phương pháp tiếp cận non-pareto.



14

Chương 3:
CƠ SỞ LÝ THUYẾT
3.1. Các lý thuyết cơ sở
3.1.1. Mơ hình điều độ job shop
Bài tốn job shop được mơ tả là có một tập gồm n cơng việc, mỗi cơng việc
có trình tự ngun cơng khác nhau tại mỗi máy, tổng số máy cho n công việc là m máy.
Bài toán điều độ được ký hiệu như sau α| β| γ, [3]. Trong mơ hình job shop ý nghĩa của
các ký tự trên là:
α: vùng biểu diễn mô hình bài tốn và ràng buộc thuộc về máy gia cơng, Jm
là bài tốn job shop có m máy, FJm là bài tốn flexible job shop có m khu vực gia cơng,
khu vực gia cơng sẽ có nhiều máy có tính năng tương tự.
β: vùng biểu diễn cho cơng việc và ràng buộc bắt buộc, ví dụ rj thể hiện
thời gian đến khác nhau của mỗi công việc, sijk thể hiện sự phụ thuộc thời gian set up
cho mỗi công việc, rcrc thể hiện cơng việc có thể quay lại gia công trên một máy.
γ: thể hiện hàm mục tiêu của mơ hình, các hàm mục tiêu thường là Cmax cực
tiểu thời gian hoàn thành, ΣwjTj cực tiểu tổng trọng số thời gian trể của công việc , hoặc
là các hàm mục tiêu được đặt ra theo nhu cầu.
Lời giải của bài toán là một kế hoạch sắp xếp thứ tự các công việc tại từng
máy để đạt được lời giải cho hàm mục tiêu. Lời giải được đánh giá qua hai chỉ tiêu độ
lệch so với điểm tối ưu và thời gian có thể đưa ra lời giải.
3.1.2. Các hướng tiếp cận giải bài toán job shop
Lịch sử ngành điều độ được khai sinh bởi Henry Laurence Gantt, năm 1918
ơng đưa ra một biểu đồ trình bày sắp xếp theo trục thời gian của các công việc. Năm
1963, Fisher and Thompson đưa ra các bài toán mẫu về job shop như FT06, FT10 nhằm
làm cơ sở đánh giá giữa các giải thuật. Đến nay số lượng các bài toán mẫu đã có là 82
bài. Các giải thuật được ghi nhận là hiệu quả đối với bài toán job shop hiện nay như

sau:


15

Về ràng buộc logic, job shop được trình bày dưới dạng đồ thị bị ràng buộc
bởi các hướng. Dùng “disjuntive programming” để giải sẽ đạt được lời giải tối ưu cho
hàm mục tiêu nhưng thời gian giải phụ thuộc vào các tham số bài tốn.
Về tính chất đặc trưng ràng buộc của bài toán job shop, hai giải thuật kinh
nghiệm quy hoạch ràng buộc (constraint programming) và xác định điểm tắt ngẽn
(shifting bottleneck) được áp dụng rộng rãi vì đưa ra lời giải gần với tối ưu và thời gian
giải có thể chấp nhận được.
Về tính chất thời gian để giải cho bài tốn, đối với các bài tốn có kích
thước lớn, hướng tiếp cận bằng cách dùng các phương pháp dị tìm trong miền khơng
gian lời giải như nhánh và chặn (Branh and Bound BnB), tìm kiếm vùng cấm (Tabu
Search TS), mô phỏng ủ (Simulated Annealing SA), giải thuật di truyền (Genetic
Algorithm GA). Các phương pháp dị tìm được xác định là phù hợp với môi trường
jobshop. Mỗi giải thuật đều có điểm mạnh riêng và được linh động áp dụng kết hợp để
tìm thấy lời giải.
3.1.3. Các ưu khuyến điểm của các giải thuật:
Điểm quan trọng của mô hình là xác định được miền khả thi. Tùy thuộc vào
khơng gian lời giải ta có thể lựa chọn chiến thuật để áp dụng. Đối với bài toán job shop
miền khả thi là rời rạc, các kỹ thuật áp dụng sẽ là công cụ “sắp xếp và lựa chọn”
(Ranking and Selection) phù hợp khi miền khả thi nhỏ. Khi miền khả thi lớn, kỹ thuật
“lựa chọn ngẫn nhiên” (Random Search) là phương pháp dị tìm tồn cục. Kỹ thuật này
tốn nhiều thời gian cho lời giải nhưng mang lại những kết quả bất ngờ. Để giảm thời
gian tính tốn, miền khả thi sẽ được giảm khi ta xác định rõ yêu cầu của hàm mục tiêu,
“giải thuật di truyền” (Genetic Algorithm) tỏ ra ưu thế trong dị tìm tồn cục [4]. Các
kỹ thuật “kinh nghiệm” (Metaheuristic) có ưu thế trong việc khống chế thời gian giải,
tuy dị tìm trong miền lân cận nhưng khi được thiết kế phù hợp vẫn cho được kết quả

gần với vùng tối ưu của không gian lời giải. Giải thuật “Tabu Search” được đánh giá là
hiệu quả trong các bài tốn điều độ. Ngồi ra, do đặc trưng của bài toán job shop giải
thuật “Shifting Bottleneck” có khả năng định hướng được lời giải theo hàm mục tiêu.
3.1.4. Mơ hình tốn của bài tóan job-shop:
Mơ hình bài tốn, ta ký hiệu:


16

Gọi i là công việc cụ thể trong tập n công việc.
Gọi j là máy cụ thể trong tập m máy.
Gọi Oij là nguyên công của việc i trên máy j và Oi,j+1 là nguyên công tiếp theo
của việc i được thực hiện tại máy là j+1
Gọi Pij là thời gian thực hiện của nguyên công Oij.
Gọi tij là thời điểm bắt đầu thực hiện nguyên công Oij, t=0 là thời điểm bắt
đầu điều độ cho tập n công việc.
Gọi Ci là thời gian hồn thành cơng việc i, thời gian hồn thành cho ngun
cơng Oij sẽ là Cij = tij + Pij.
Gọi Cmax là hàm max(Ci), chính là thời gian hồn thành cho n cơng việc.
Hàm mục tiêu của bài toán là min(Cmax).
Các giá trị đều là nguyên dương, đây là bài tốn thuần nhất cho mơ hình jobshop.
Mơ hình tốn theo quy hoạch tuyến tính:
Hàm mục tiêu: min(Cmax)
Các ràng buộc:
Cmax ≥ tin + Pin.

(1) với mọi i, trong đó n là máy thực hiện ngun

cơng cuối của việc i.
ti,j+1 ≥ tij + Pij.


(2) vói mọi j, trong đó i là công việc cụ thể.

tk,j ≥ tij + Pij
hoặc ti,j ≥ tkj + Pkj

(3) với mọi i, k là hai việc khác nhau trong tập n

việc, trong đó j là máy cụ thể
Ràng buộc thứ 1 xác định thời gian hồn thành n cơng việc. Ràng buộc thứ 2
là ràng buộc trước sau của nguyên công. Ràng buộc thứ 3 là thứ tự điều độ của các việc
trên một máy.
3.1.5. Kỹ thuật mơ hình hóa và mơ phỏng trong sản xuất:
Mô phỏng là sự giả lập hoạt động của hệ thống thực và không phụ thuộc vào
thời gian thực. Ưu điểm nổi bật của mô phỏng là qua quan sát những giá trị có được của
mơ hình giả lập, ta có thể dự đốn điều gì sẽ xảy ra tương tự đối với hệ thống thực. Mô
phỏng là một công cụ giúp ta hạn chế được ảnh hưởng của các yếu tố ngẫu nhiên trong
mơi trường thực. Nói cách khác, một lời giải tối ưu chỉ có được trong môi trường tất


17

định và khi áp dụng lời giải này vào môi trường thực thì khơng đảm bảo cho kết quả tối
ưu. Do đó các lời giải cần được kiểm chứng bằng mô phỏng trước khi áp dụng vào môi
trường thực để làm tăng độ tin cậy cho lời giải. Khái niệm mơ phỏng tối ưu được hiểu
theo ý nghĩa trên. Đó là quá trình tìm lời giải tốt nhất trong một tập lời giải được thực
hiện tính tốn trong mơi trường mô phỏng.
Các bước cần thực hiện để đảm bảo mô phỏng có giá trị sử dụng:
Thành lập vấn đề


Thu thập số liệu và
định nghóa mô hình

Mô hình
có giá
trị?

Không

Có
Xây dựng chương trình
máy tính và kiểm tra

Thử nghiệm

ù

Chương
trình
Có giá trị?

Không

Có
Thiết kế thực nghiệm
Thực hiện mô phỏng
Phân tích kết quả
Lưu trữ kết quả và
ứng dụng


Hình 3-1: Các bước cần thực hiện một bài tốn mơ phỏng
(nguồn tham khảo [1])
3.2. Khái niệm mơ phỏng tối uu.
Mô phỏng tối ưu là kỹ thuật kết hợp giữa kỹ thuật dị tìm (metaheuristic)
và kỹ thuật mơ phỏng (simulation model) nhằm để tìm lời giải cho các vấn đề có hàm
mục tiêu khó khăn hay khơng thể tính trực tiếp được. Mơ hình mơ phỏng được sử dụng


18

như là cơng cụ tính tốn cho hàm mục tiêu. Các bước thực hiện mô phỏng tối ưu như
sau:
Bước 1: Bắt đầu từ lời giải đầu tiên
Bước 2: Dùng mô hình mơ phỏng để tính giá trị cho hàm mục tiêu.
Bước 3: Điều chỉnh lời giải cho trước theo kỹ thuật dị tìm.
Bước 4: Lặp lại bước 2 cho đến khi đạt điều kiện dừng.
Sơ đồ sau cho ta nguyên lý tích hợp tối ưu và mơ phỏng,
Chạy mơ
phỏng
Tiêu chuẩn hóa
hàm mục tiêu

Tính hàm
fitness

GA

Chọn lọc cá
thể


Phát ra
lời giải

Lai ghép và
đột biến

Hình 3-2: Sơ đồ q trình mơ phỏng được dẫn hướng bởi GA
(nguồn tham khảo [2])


19

Sơ đồ chi tiết dùng giải thuật di truyền kết hợp với mô phỏng tối ưu như sau:
Bắt đầu

Thế hệ thứ t
Mã hóa khơng
gian lời giải

Xác định tham
số đầu tiên

Tạo quần thể
đầu tiên

Chọn ngẫu
nhiên

Cá thể thứ 1
Cá thể thứ 2

Cá thể thứ n

Thực hiện mơ phỏng
với từng cá thể

Tính độ chặt chẽ cho
từng cá thể

Sai

Dừng?
Đúng

Tạo quần thể kế tiếp
Kết thúc

Hình 3-3: Sơ đồ kết hợp giữa kỹ thuật di truyền và mô phỏng tối ưu
(Nguồn tham khảo [10])


20

Chương 4:
XÂY DỰNG CƠNG CỤ TÍCH HỢP TỐI ƯU MƠ PHỎNG
4.1. Khơng gian tìm kiến lời giải
4.1.1. Biểu diễn bài tốn job-shop trong giải thuật di truyền
Chuỗi gen mã hóa có chiều dài bằng tổng số ngun cơng cần thực hiện cho
bài tốn. Chuỗi sẽ có n ký tự thể hiện cho n công việc và mỗi ký tự sẽ lặp lại với số lần
bằng đúng số nguyên công cần thực hiện cho việc đó (job permutation with repetion).
Vị trí của các ký tự trên chuỗi là không hạn chế (un-partitioned operation based

representation), do đó cần một bộ biên dịch để giải mã thành một lịch điều độ tích cực.
Cơ chế giải mã được minh họa theo ví dụ sau trong bài tốn có 3 cơng việc và 3 máy
gia cơng
Một chuỗi mã hóa

1

Lịch điều độ

M1

tương ứng

M2

3

1

2

1

2
3

3

2


2

1

3

1

3

3
1

M3

2
2

Hình 4-1: Hình ảnh mơ tả chuỗi mã hóa bài tốn 3x3 job-shop.
Bộ biên dịch hoạt động như sau, căn cứ vào trình tự thực hiện nguyên công
của việc 1 đã cho trước trước là [M1, M2, M3], gen mã hóa cơng việc 1 là “1” trong
chuỗi gen sẽ được điền vào các hàng tương ứng là máy gia công. Sau khi thực hiện cho
tất cả cơng việc, ta có bảng điều độ như trên. Theo đó, máy 1 (M1) sẽ thực hiện theo
tuần tự các công việc là [1,2,3], máy 2 (M2) sẽ thực hiện tuần tự các công việc [3,1,2]
và máy 3 (M3) sẽ thực hiện tuần tự các công việc [2,1,3].
4.1.2. Lịch điều độ tích cực cho chuỗi gen
Định nghĩa điều độ tích cực (active schedule) là một lịch điều độ trong miền
điều độ khả thi, với một lịch điều độ tích cực khơng có ngun cơng nào được điều độ
sớm hơn mà khơng ảnh hưởng đến thời gian hồn thành của ít nhất một ngun cơng
khác. Một miền điều độ khả thi được tạo bởi các lịch điều độ khả thi. Điều độ khả thi



21

(feasible schedule) là một lịch điều độ thỏa mãn ràng buộc trước sau theo nguyên công
của công việc.
Dựa trên nguyên tắc chuyển về bên trái của một nguyên công không ảnh
hưởng đến thời gian hoàn thành của bất kỳ nguyên công khác. Cơ chế sau cho ta một
lịch điều độ tích cực đối với chuỗi gen mã hóa ở trên:
Bước 1: Căn cứ thứ tự trên chuỗi gen, điều độ nguyên công chưa được điều
độ vào bên trái của chuỗi thời gian..
Bước 2: Kiểm tra khoảng thời gian trống giữa thời gian hồn thành của
ngun cơng trước của cơng việc và thời gian bắt đầu của các
nguyên công đã được điều độ trên máy.
Bước 3: Nếu khoảng thời gian rỗi này lớn hơn thời gian gia công của nguyên
công mới được điều độ, thì di chuyển ngun cơng này về khoảng
trống đó. Thực hiện việc nhảy gen về bên trước trên chuỗi gen.
Bước 4: Tiếp tục thực hiện điều độ cho các nguyên công tiếp theo. Kết quả là
một chuỗi gen mới khi thực hiện với bộ biên dịch ở trên sẽ cho ra
một lịch điều độ tích cực.
4.1.3. Lịch điều độ tích cực tồn phần:
Khái niệm điều độ tích cực toàn phần được Chaoyong, [7], đề xuất. Tác giả
quan sát, một lịch điều độ tích cực khi được điều độ ngược lại (reverse) theo trình tự kỹ
thuật đảo chiều thì lịch điều độ ngược này có thể khơng thuộc tập điều độ tích cực. Một
lịch điều độ tích cực tồn phần khi có lịch điều độ và lịch điều độ ngược đều là một lịch
điều độ tích cực. Hình ảnh sau giới thiệu một lịch điều độ tích cực toàn phần.


22


Thực hiện
đảo ngược

Một lịch điều độ khơng tích cực

Một lịch điều độ tích cực

Thực hiện di
chuyển về trái
Thực hiện
đảo ngược

Một lịch điều độ tích cực
(tồn phần)

Một lịch điều độ tích cực
(tồn phần)

Hình 4-2 : Giới thiệu một lịch điều độ tích cực tồn phần
(nguồn tham khảo [7])
Cơ chế để tạo được lịch điều độ tích cực tồn phần: dùng một lịch điều độ
tích cực được đảo ngược và thực hiện điều độ tích cực cho lịch đảo ngược này. Khi thời
gian hoàn thành của hai lịch điều độ trên là bằng nhau, ta được một lịch điều độ tích
cực tồn phần.
Ưu điểm của lịch điều độ tích cực tồn phần là làm cho miền khơng gian tìm
lời giải giảm xuống. Hình ảnh sau mơ tả miền khơng gian tìm kiếm của bài toán điều
độ:


23

Miền lịch điều độ khả thi

Miền điều độ nữa tích cực
Miền điều độ tích cực
Miền tích cực tồn phần
Miền máy khơng
chờ ngun cơng
Miền
tối ưu

Hình 4-3: Hình mơ tả vùng chứa lịch điều độ tối ưu bài toán job-shop
4.2. Giải thuật di truyền lai cho bài toán jobshop
4.2.1. Biểu điễn chuỗi gen
Chuỗi gen được mã hóa theo cơng việc và được lặp lại bằng số ngun cơng
khơng giới hạn vị trí như trình bày ở phần trên.
4.2.2. Lai tạo
Hai cá thể con được hình thành với sự thừa hưởng thứ tự vị trí của một cơng
việc trên gen bố hoặc mẹ. Với n cơng việc được mã hóa, ứng với một cặp bố mẹ thì số
lượng con tối đa được sinh ra là 2n cá thể.
p1: [ 3 2 2 2 3 1 1 1 3 ]
p2: [ 1 1 3 2 2 1 2 3 3 ]
khi lai tạo với việc “2” được lựa chọn, hai cá thể con được sinh ra như sau:
c1 thừa hưởng “2” từ p1 có chuỗi gen : [ 1 2 2 2 1 3 1 3 3 ], chuỗi gen này
được hình thành với thứ tự vị trí của việc “2” từ p1 và thứ tự của các công việc khác
theo p2.
Tương tự ngược lại cá thể c2 sẽ có chuỗi gen: [ 3 3 1 2 2 1 2 1 3 ]