BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC LẠC HỒNG
*** NGUYỄN HỮU THIÊN ÂN ỨNG DỤNG MÔ HÌNH JOB-SHOP LINH ĐỘNG ĐỂ HỖ
TRỢ LẬP LỊCH SẢN XUẤT CHO MỘT CÔNG TY
Chuyên ngành Công Nghệ Thông Tin
Mã số: 60.48.02.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Giáo viên hướng dẫn: PGS. TS. Trần Văn Lăng Một lần nữa, tôi xin khẳng định về sự trung thực của lời cam kết trên.

MỤC LỤC
Trang
Trang phụ bìa
LỜI CẢM ƠN

LỜI CAM ĐOAN

DANH MỤC CÁC TỪ VIẾT TẮT

DANH MỤC BẢNG

DANH MỤC HÌNH

CHƯƠNG 1: GIỚI THIỆU TỒNG QUAN 1

1.1.

Tổng quan về bài toán lập lịch: 1

1.1.1.

Bài toán lập lịch Job shop: 1


Giai đoạn thứ 3: 8

CHƯƠNG 2:MỘT SỐ VẤN ĐỀ HỖ TRỢ LẬP LỊCH TRONG SẢN XUẤT . 10

2.1.

Ý nghĩa lập kế hoạch sản xuất: 10

2.2.

Mô hình dữ liệu: 13

2.3.

Mô hình sản xuất: 15

2.3.1.

Phân loại theo hình thức tổ chức sản xuất: 16

a.

Sản xuất liên tục (Flow shop): 16

b.

Sản xuất gián đoạn (Job shop): 16

c.



2.5.2.

Các luật phân phối Heuristics: 24

2.5.3.

Thuật toán di truyền (Genetic algorithms): 25

2.5.4.

Thuật toán tìm kiếm Tabu (Tabu search): 28

2.5.5.

Thuật toán mô phỏng luyện kim (Simulated Annealing): 29

2.5.6.

Thuật toán tối ưu hóa thuộc địa đàn kiến (Ant Colony
Optimization) : 30

2.5.6.1.

Nguồn gốc thuật toán: 30

2.5.6.2.

Miêu tả thuật toán ACO: 33



3.1.3.3.

Giai đoạn dập viên: 43

3.1.3.4.

Giai đoạn bao phim: 43

3.1.3.5.

Giai đoạn ép vĩ hay vô chai: 43

3.1.3.6.

Giai đoạn đóng gói: 43

3.1.4.

Các yêu cầu đặt cho hệ thống lập lịch : 43

3.2.

Mô hình dữ liệu : 47

3.3.

Thuật toán lập lịch: 47

3.3.1.


4.1.

Cấu trúc hệ thống: 62

4.2.

Cơ sở dữ liệu: 62

4.3.

Giao diện: 63

4.3.1.

Màn hình đăng nhập: 63

4.3.2.

Màn hình cập nhật thông tin đơn đặt hàng: 64

4.3.3.

Màn hình cập nhật thông tin sản phẩm: 65

4.3.4.

Màn hình cập nhật thông tin máy: 65

4.3.5.


4.4.1.4.

Xét thời gian thực hiện trên các máy trạm: 71

4.4.2.

Kết quả hoán vị của thuật toán ACO: 78

4.4.3.

So sánh kết quả lập kế hoạch mặc định với kết quả của thuật
toán ACO: 81

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

TÀI LIỆU THAM KHẢO

PHỤ LỤCDANH MỤC CÁC TỪ VIẾT TẮT
Từ viết tắt Nguyên văn Ý nghĩa
ADI Advance demand information Thông tin nhu cầu ứng
trước
ACO Ant Colony Optimization Tối ưu hóa thuộc địa đàn
kiến
MPCS manufacturing planning and control
systems
Lập kế hoạch sản xuất và hệ

Bảng 4.4. Mô tả thời gian thiết lập cần thiết trên máy trạm mỗi khi hoàn tất một sản
phẩm. 70

Bảng 4.5. Mô tả thời gian biểu được tạo ra từ hệ thống lập kế hoạch. 71

Bảng 4.6. Mô tả thời gian bắt đầu và thời gian kết thúc cho tất cả các sản phẩm. 73

Bảng 4.7. Mô tả thời gian bắt đầu và thời gian kết thúc cho tất cả các sản phẩm. 74

Bảng 4.8. Mô tả thời gian bắt đầu và thời gian kết thúc cho tất cả các sản phẩm. 75

Bảng 4.9. Mô tả thời gian bắt đầu và thời gian kết thúc cho tất cả các sản phẩm. 75

Bảng 4.10. Mô tả thời gian bắt đầu và thời gian kết thúc cho tất cả các sản phẩm. . 76

Bảng 4.11. So sánh lịch trình mặc định với lịch trình tối ưu 81

Bảng 4.12. So sánh lịch trình mặc định của tháng 4,5,6,7 với lịch trình tối ưu tháng
4,5,6,7 82
DANH MỤC HÌNH
Trang
Hình 1.1. Một thể hiện cho bài toán Job-shop 5

Hình 1.2. Sơ đồ giai đoạn thứ 1. 7


Hình 3.3. Mô hình biểu hiện lập kế hoạch sản xuất 46

Hình 3.4. Mô hình biểu hiện dữ liệu sản xuất 47

Hình 3.5. Mô hình xử lý n công việc trên m máy trạm theo thuật toán Jobshop 51

Hình 3.6. Mô hình lập lịch đẩy trong dây chuyền sản xuất 52

Hình 3.7. Mô hình xử lý n công việc trên m máy trạm theo thuật toán đẩy 54

Hình 3.8. Mô hình tối ưu hóa thuộc địa đàn kiến 57

Hình 3.9. Mô hình hiển thị biểu đồ dòng chảy của thủ tục đầu tiên vận hành hệ
thống lập kế hoạch: 59

Hình 3.10. Mô hình hiển thị biểu đồ lưu lượng của kết quả thông qua việc tối ưu
hóa bằng phương pháp ACO. 60

Hình 3.11. Một biểu đồ lưu lượng tổng thể đơn giản hóa thủ tục hoạt động hệ thống
lập kế hoạch. 61

Hình 4.1. Mô hình cơ sở dữ liệu 63

Hình 4.2. Màn hình đăng nhập 64

Hình 4.3. Màn hình thông tin đơn đặt hàng. 64

Hình 4.5. Màn hình thông tin máy 65


Với sự đa dạng của bài toán lập lịch chẳng hạn như: lập lịch quản lý một dự
án, lập lịch xếp lớp cho giáo viên, lập lịch sản xuất và lập lịch trong các loại ngành
nghề khác nhau. Trong chương này nghiên cứu về bài toán lập lịch sản xuất. Do có
một tính chất chung trong bài toán lập lịch sản xuất thường được mô tả dựa trên ba
tính đặc tính như: công việc, môi trường máy và tiêu chuẩn tối ưu. Sự phân loại này
đang dùng rộng rãi được giới thiệu qua nhiều tài liệu nghiên cứu [19]
1.1.1. Bài toán lập lịch Job shop:
Trong cuối những năm 1950, B.Gi er và GLThompson trong bài báo có tiêu
đề "Các thuật toán để giải quyết các vấn đề kế hoạch sản xuất" [6] cho rằng nó
không phải là cần thiết để tìm kiếm cho một lịch trình tối ưu trên tất cả các lịch trình
có thể, nhưng chỉ hơn một tập hợp tiến độ khả thi, được gọi là lịch trình hoạt động
sản xuất.
Vấn đề lập lịch sản xuất jobshop cổ điển có thể được xây dựng như sau:
-2-
Một M tập hợp các máy m có M
1
, …, M
m
và tập hợp J của n công việc J
1
,
…, J
n
. Công việc J
j
bao gồm n
j
công đoạn
O
ij

) của
thời gian bắt đầu của cả các công đoạn O
ij
. Lịch trình S có thể là:
− S
ij
+ p
ij
≤ S
i+1,j
với mọi hoạt động (ưu tiên hạn chế giữa hoạt động của cùng
một công việc).
− S
ij
+p
ij
≤ S
uv
hoăc S
uv
+ p
uv
≤ S
ij
cho tất cả các cặp O
ij
,O
uv
với µ
ij

đoạn được thực hiện trên M
k
Thể hiện công việc chung J
j
được thực hiện trên các công đoạn O
ij
với O
1j
, ,

thường được đặc trưng bởi các yếu tố sau:
− Thời gian xử lý p
ịj
cần thiết để xử lý công đoạn i của công việc J
j

− Tâp hợp các máy M
ij
đủ điều kiện cho công đoạn O
ij

− Ngày bắt đầu r
j
là thời gian khi công đoạn đầu tiên của công việc J
j
được xử
lý
− Ngày kết thúc d
j
là thời gian hoàn thành công việc J

công việc C
max
(thời gian hoàn thành của tất cả các công việc trên tất cả các
máy) hoặc giảm thiểu thời gian tổng lưu lượng trung bình có trọng (thời gian
trung bình các công việc vẫn còn trong máy).
Với ký hiệu ba trường này, nó có thể phân loại và là tài liệu tham khảo
nhanh chóng cho tất cả các biến thể của các vấn đề lập kế hoạch

Việc lập lịch biểu có thể được biểu hiện bằng biểu đồ Gantt, là một kỹ thuật
đồ họa đơn giản phù hợp cho các tình huống ít phức tạp. Điều này không cung cấp
bất kỳ quy tắc nào cho việc lựa chọn, nhưng chỉ đơn giản là trình bày một kỹ thuật
-4-
đồ họa cho kết quả hiển thị và tiến độ và kết quả đánh giá (makespan, thời gian
nhàn rỗi, thời gian chờ đợi, máy sử dụng, vv).
Để làm rõ hơn cho bài toán Jopshop này, ví dụ sau đây sẽ thể hiện việc lập
kế hoạch sản xuất trên các máy được thể hiện qua biểu đồ Gantt như sau:
Ví dụ:
Một trường hợp cụ thể cho bài toán lập lịch job-shop như sau: có 5 công
việc (jobs) được xử lý trên 2 máy (machine), mỗi công việc phải được bắt đầu từ
máy 1 sau đó mới đến máy 2.
Như vậy: J=5, M= {M1, M2}
Thời gian xử lý công việc trên các máy như bảng sau:
Bảng 1.1. Thể hiện công việc trên các máy theo thuật toán Job-shop
Công việc
(job)
Máy 1
(machine1)
Máy 2
(machine2)
1 13 3

cho thấy không khả thi. Việc tìm kiếm lộ trình sản phẩm trong số tất cả các tuyến
đường chưa cụ thể và rõ ràng. Dẫn đến vấn đề khó khăn trong việc quản lý lập kế
-6-
hoạch sản xuất. Trong môi trường làm việc thực tế, lộ trình sản phẩm khác nhau
đóng một vai trò quan trọng, đặc biệt là cho sản xuất một loạt các sản phẩm cùng
một lúc. Luận văn này mô tả sự phát triển của một hệ thống lập kế hoạch tạo ra sản
phẩm có thể tất cả các tuyến đường. Hệ thống lập kế hoạch hoạt động dựa trên khái
niệm lập kế hoạch đẩy. Sau đó, với sự trợ giúp của thuật toán tối ứu hóa đàn kiến
(Ant Colony Optimization
)
tất cả các tuyến sản phẩm có thể được đánh giá theo
tổng số thời gian lập kế hoạch sản phẩm.
1.2.1. Mục tiêu của luận văn:
Mục tiêu của luận văn là áp dụng mô hình lập lịch trên lý thuyết dựa trên
thuật toán ACO và mô hình phù hợp để đưa vào thực tế sản xuất.
Giúp doanh nghiệp có thể rút ngắn thời gian sản xuất xuống còn vài ngày,
thậm chí vài giờ. Điều đặc biệt, doanh nghiệp sản xuất luôn ở trong thế chủ động
với các phương án khác nhau, không lệ thuộc vào sự biến đổi của quá trình sản
xuất. Tiết kiệm cả về thời gian lẫn công sức và sẽ mang đến lợi ích cao hơn về mặt
quản lý và lợi nhuận.
Giúp doanh nghiệp có thể dễ dàng quản lý sản xuất thông qua biểu đồ Gantt
trong việc lập kế hoạch sản xuất cũng như thay đổi kế hoạch.
1.2.2. Nội dung trình bày luận văn:
Với mục tiêu và các công việc được trình bày như trên, cấu trúc của luận văn
được trình bày như sau:
Chương 1. Giới thiệu tổng quan.
Chương 2. Một số vấn đề hỗ trợ lập lịch trong sản xuất.
Chương 3. Hệ thống lập lịch trong sản xuất.
Chương 4. Cài đặt và thử nghiệm các chức năng của chương trình.
Kết luận và hướng phát triển

-8-
thông tin từ doanh nghiệp nghiên cứu sẽ được sử dụng làm tài liệu tham khảo trong
việc phát triển hệ thống lập kế hoạch .
Hình 1.3. Sơ đồ giai đoạn thứ 2
iii. Giai đoạn thứ 3:
Giai đoạn này sẽ thảo luận về các phương pháp đề để đạt các mục tiêu đã
nêu. Bao gồm làm thế nào để phát triển một hệ thống lập kế hoạch trên máy vi tính
Xem xét lý thuyết
Nhận xét hệ thống lập kế hoạch hiện tại:
1. Lập kế hoạch công việc (Job shop scheduling)
2. Lập kế hoạch theo kiểu đẩy (Push scheduling)
3. Lập kế hoạch theo kiểu kéo (Pull scheduling)
Hình 1.4. Sơ đồ giai đoạn thứ 3.
Khái niệm thiết kế
phát triển phần
mềm
Lựa chọn
ngôn ngữ lập
trình
Cơ cấu hệ thống cơ
sở dữ liệu dựa trên
các dữ liệu thu thập
Xây dựng và xem xét
các thuật toán lập lịch
trình và công nghệ tự
động
Xem xét lại hệ thống
giao diện người dùng
hiện có và cơ cấu giao
diện hệ thống
Phát triển hệ thống phần mềm và
mã code
Phân tích thử nghiệm hệ thống lập
kế hoạch và các chức năng

Đơn đặt hàng
-11-
− Người lập kế hoạch Sản xuất xem xét đơn đặt hàng của khách hàng dựa trên
khung thời gian yêu cầu, tầm quan trọng khách hàng và năng lực sản xuất có
sẵn. Họ làm việc chặt chẽ với doanh số bán hàng và tiếp thị để đáp ứng mong
đợi của khách hàng và tối đa hóa doanh số bán hàng.
Thành phần
− Lập kế hoạch sản xuất bao gồm ra lệnh cho bộ phận sản xuất khối lượng
hàng hoá sản xuất, lập kế hoạch nhân sự, để chế biến sản xuất và ngày đến
hạn. Sản xuất lập kế hoạch sắp xếp cần thiết giảm thời gian bảo trì thường
xuyên và làm sạch.
Nhân viên
− Lập kế hoạch sản xuất cố gắng để tối đa hóa các nhân viên thông qua luân
chuyển công việc, lịch trình nghỉ ngơi hiệu quả, qua đào tạo và cơ hội làm
việc theo nhóm. Một sự cân bằng giữa công việc hoạt động quy trình, đào tạo
và nhóm tạo ra một lực lượng lao động nhiều hơn sản xuất.
Dự phòng Kế hoạch
− Thông thường, người lập kế hoạch sản xuất tạo ra kế hoạch rằng tài khoản
cho các vấn đề tiềm năng, chẳng hạn như mất tài nguyên, máy và tình trạng
thiếu việc làm, do đó, nhân viên và quản lý biết những hành động khi đối mặt
với một trục trặc bất ngờ trong sản xuất.
Phần mềm
− Hầu hết các công ty sản xuất phần mềm quy mô lớn sử dụng mạnh mẽ cho
lập kế hoạch, trong đó phải chiếm nhiều khó khăn phức tạp và mức độ thông
tin đa dạng. Phần mềm phổ biến bao gồm AMS dự án thời gian thực, 7
Artemis, Cando, Delmia 5, D-Opt, Hydra, Microsoft Project, Primavera.
Nhiều gói phần mềm được thiết kế phù hợp cho các ngành công nghiệp cụ
thể và có thể được sửa đổi cho các nhu cầu kinh doanh cá thể.
-12-
Ngày nay các doanh nghiệp với quy mô sản xuất ngày càng lớn, số lượng sản

doanh nghiệp lập kế hoạch nguồn tài nguyên hữu hạn và giao hàng (Stoop và Wiers,
1996). [26]
Stoop và Wiers (1996) tuyên bố rằng lập kế hoạch sản xuất là một phần của
quy hoạch và kiểm soát của các đơn vị sản xuất cá thể. Theo ông, tại mỗi trạm làm
việc trong một đơn vị sản xuất, mỗi khi một công việc được hoàn thành, các công
trình xử lý sẽ được tiếp tục bởi các trung tâm làm việc tiếp theo. Một công việc
-14-
hoàn thành là một sản phẩm mà thông qua các yêu cầu kiểm soát chất lượng và đã
được đóng gói để gửi cho khách hàng.
Quyết định này được gọi là trình tự sản xuất. Sự tồn tại của một quyết định
trình tự rõ ràng trên dòng chảy công việc phụ thuộc vào cách thức lập kế hoạch
được thực hiện.Vì vậy việc phân biệt được thực hiện giữa hai cấp độ tập hợp có thể
lập kế hoạch:
i. Tài nguyên cấp công việc liên quan đến việc lập kế hoạch cho mỗi tài
nguyên (máy trạm). Đây là loại lập kế hoạch được đưa ra không có
trình tự bởi quyết định của các xưởng.
ii. Đơn vị sản xuất cấp công việc chỉ được lên kế hoạch cho tổng số đơn
vị sản xuất. Các hoạt động của công việc không được dự kiến. Đây là
loại lập kế hoạch được quyết định trình tự của các phân xưởng.
Mối quan hệ lý thuyết giữa lập kế hoạch, quy hoạch và trình tự có thể được
mô tả như hình 2.2.
Hình 2.2. Minh hoạ về kế hoạch, lịch trình và trình tự.(Stoop năm 1996)
Trong thực tế việc thực hiện kế hoạch hoặc dự kiến của các đơn vị sản xuất
thường sai lệch từ việc thực hiện. Hầu hết những sai lệch là tiêu cực, có nghĩa là
hiệu suất thực tế còn tồi tệ hơn so với hiệu suất dự kiến. Rõ ràng, kỳ vọng về biểu
hiện thông thường quá lạc quan. Trên dòng chảy sản xuất nhiễu loạn hàng ngày gây
-15-
ra những sai lệch về hiệu suất như thể hiện trong bảng 2.1. Những nhiễu loạn có thể
được chia thành ba loại:
Bảng 2.1. Các nhiễu loạn trong nhà máy