ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH
THUẬT TOÁN
&
PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
GVHD: PGS. TS. ĐỖ VĂN NHƠN
HVTH: ĐOÀN VĂN HUYÊN CH1301091
TP HCM, tháng 10 năm 2014
NHẬN XÉT CỦA GIẢNG VIÊN



VẤN
ĐỀ LẬP
LỊCH
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên

MỤC LỤC
Lời mở đầu trang 4
Vấn đề lập lịch trình sản xuất trang 5
I. Đặt vấn đề trang 5
2
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
II. Xây dựng giải pháp trang 6
1. Mô hình hóa vấn đề trang 6
1.1. Vấn đề thực tế và vấn đề cần giải quyết trang 6
1.2. Xây dựng mô hình trang 8
2. Thiết kế thuật giải trang 11
II.1.Lựa chọn phương pháp trang 11
II.2.Ý tưởng cho thuật giải trang 12
II.3.Mô tả cụ thể trang 18
II.4.Thuật giải trang 19
3. Chứng minh tính hiệu quả trang 27
4. Kiểm chứng thực nghiệm trang 27
5. Những tồn tại và hướng cải tiến trang 29
III Kết luận
trang 30
Tài liệu tham khảo trang 31
3
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
LỜI MỞ ĐẦU
Trong cuộc sống, con người luôn gặp phải những vấn đề, những khó khăn, những

vướng mắc cần phải giải quyết. Đôi khi những vấn đề ấy khá đơn giản và có thể giải
quyết một cách dễ dàng. Nhưng vẫn tồn tại những vấn đề vô cùng phức tạp, muốn giải
quyết được con người phải bỏ ra rất nhiều công sức và nguồn lực. Với sự tiến bộ khoa
học, kỹ thuật đặc biệt là trong khoa học máy tính, đã mang lại cho con người rất nhiều
công cụ, ứng dụng hữu ích. Những công cụ ấy giúp con người giải quyết được rất nhiều
vấn đề từ đơn giản đến phức tạp, từ nhỏ đến lớn.
Tuy nhiên, vẫn còn nhiều vấn đề vô cùng phức tạp từ cuộc sống đang thách thức
các nhà khoa học máy tính tìm tòi, nghiên cứu các phương pháp mới, thuật toán mới,
thuật giải mới, để giải quyết chúng.
4
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
VẤN ĐỀ LẬP LỊCH TRÌNH SẢN XUẤT
I. Đặt vấn đề
Tại một công ty sản xuất hàng may mặc, có nhiều phân xưởng sản xuất và
mỗi phân xưởng đảm nhiệm một vai trò nhất định trong quá trình sản xuất ra
thành phẩm. Trong đó có thể chia ra hai bộ phận chính:
- Cắt: từ bảng thiết kế một mặt hàng và nguyên vật liệu sẳn có, các công
nhân sẽ cắt nguyên vật liệu ra thành những phần khác nhau của mặt
hàng, tạo ra những bán thành phẩm chờ thực hiện tiếp ở bước tiếp theo.
- Ráp: từ những bán thành phẩm (bộ phận đã được cắt), các công nhân
may chúng lại với nhau để được một thành phẩm hoàn chỉnh chờ kiểm
nghiệm và giao cho khách hàng.
Ngoài ra còn những bộ phận khác như: thu mua nguyên vật liệu, kiểm tra
chất lượng thành phẩm, tính toán giá thành thành phẩm, kinh doanh,…
Vấn đề được đặt ra ở đây là làm sao tối ưu quá trình sản xuất, giảm thiểu
chi phí, tăng năng suất sản xuất để kinh doanh đạt hiệu quả và thu được lợi
nhuận cao.
Đòi hỏi nhà quản trị, điều hành phải biết sắp xếp lịch trình sản xuất một
cách khoa học, hợp lý và chặt chẽ.
Lập lịch trình sản xuất phải đảm bảo cho các công việc được thực hiện một

cách hiệu quả, với các yêu cầu:
- Đáp ứng thời gian giao hàng cho khách hàng
- Giảm thiểu việc trễ hạn
- Giảm thiểu thời gian rỗi của các phân xưởng
- Giảm thiểu nguyên vật liệu tồn kho dở dang, chỉ thu mua nguyên vật
liệu khi cần, và không xảy ra tình trạng thiếu nguyên vật liệu
- Tăng cường năng suất lao động của công nhân hoặc máy móc
- Giảm thiểu thời gian hoàn thành một đơn hàng
Cần phải có một hệ thống lập lịch trình sản xuất nhằm mục tiêu điều hành
và nâng cao hiệu quả sản xuất, cũng như có phương án tối ưu cho việc thu
mua nguyên vật liệu, lập kế hoạch giao hàng cho khách hàng.
5
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
II. Xây dựng giải pháp
1. Mô hình hóa vấn đề
1.1. Vấn đề thực tế và vấn đề cần giải quyết
a. Khảo xác và thu thập dữ liệu, thông tin và tri thức
- Lấy thông tin các phân xưởng sản xuất và chức năng của các
phân xưởng đó (cắt hay ráp)
- Lấy thông tin năng suất làm việc của mỗi phân xưởng, mỗi ngày
làm ra được bao nhiêu thành phẩm, bán thành phẩm,… kể cả
thông tin số lượng thành phẩm lỗi, không sử dụng được,…
- Lấy thông tin các đơn hàng (số lượng mặt hàng, thời gian giao
hàng,…)
- Lấy thông tin các ca làm việc chính thức và tăng ca, thời gian
tăng ca tối đa
b. Chọn lọc, chuẩn hóa, xác định cơ sở cho dữ liệu, thông tin và tri
thức
- Phân xưởng: loại phân xưởng, năng suất sản xuất
- Đơn hàng: số lượng mặt hàng, hạn giao hàng

c. Phạm vi, giới hạn
- Lập ra lịch trình sản xuất, tối ưu vấn đề phân bổ thời gian làm
việc cho các phân xưởng, đáp ứng tiến độ giao hàng
- Có thể chậm trễ tiến độ giao hàng nhưng phải tối ưu nhất (thời
gian chậm trễ là thấp nhất)
- Đề xuất được phương án tăng ca trong giới hạn cho phép để đẩy
nhanh tiến độ khi cần thiết
- Chỉ lập lịch sản xuất, tăng ca, không lập lịch thu mua nguyên vật
liệu, lịch giao hàng, lịch kiểm tra thành phẩm,…
d. Giả thiết của vấn đề
- Thời gian sản xuất một mặt hàng là như nhau
- Năng suất sản xuất của một phân xưởng là cố định
- Bỏ qua các thành phẩm lỗi, xem như đã tính toán vào năng suất
cố định cho mỗi phân xưởng, được tính theo công thức:
Năng suất = số lượng sản xuất thực tế - số lượng lỗi
- Thời gian giao hàng được tính ra trước (ngày thứ bao nhiêu kể từ
lúc bắt đầu lịch trình), được tính theo công thức:
6
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
Thời gian giao = ngày dự kiến giao – ngày bắt đầu lịch
trình
- Ngày bắt đầu lịch trình luôn là ngày thứ hai của tuần
- Số đơn hàng là cố định từ lúc bắt đầu đến lúc kết thúc lịch trình
- Một tuần làm việc 6 ngày, mỗi ngày làm 8 giờ ứng với 100%
năng suất làm việc, được chia làm 2 ca (sáng và chiều) mỗi ca là
50% năng suất.
- Thời gian tối thiếu giao bán thành phẩm sau khi cắt là 1 ca
e. Mục tiêu của vấn đề
Đề xuất một hoặc một vài lịch trình sản xuất đáp ứng mục tiêu tối ưu
quá trình sản xuất, đúng tiến độ giao hàng.

f. Các ràng buộc
- Để hoàn thành sản phẩm phải trải qua hai công đoạn là cắt và ráp.
Công đoạn cắt phải được thực hiện trước, sau đó mới thực hiện
công đoạn ráp. Ví dụ: sản xuất 100 thành phẩm cần phải cắt 100
bán thành phẩm sau đó ráp 100 bán thành phẩm đó lại.
- Nếu có tăng ca thì tại mỗi phân xưởng, mỗi ngày tăng ca không
quá 2 giờ (25% năng xuất làm việc) và một tuần không quá 4 lần
tăng ca.
- Tất cả các phân xưởng điều phải làm việc, nếu có trống thì không
được vượt quá 4 giờ/ngày (1 ca).
- Tổng dòng thời gian hoàn thành tất cả đơn hàng là nhỏ nhất có
thể,
Tổng dòng thời gian = tổng thời gian sản xuất + tổng thời
gian chờ đợi
- Tổng thời gian tăng ca là thấp nhất có thể
Tổng thời gian tăng ca = sum(thời gian tăng ca của tất cả
phân xưởng)
- Tổng thời gian trống là thấp nhất có thể
Thời gian trống (trên mỗi ca, chỉ tính trên ca chính) = (năng
suất – số lượng phân công) / 4 (giờ)
Tổng thời gian trống = sum(thời gian trống) (giờ)
- Tổng thời gian trễ hạn giao hàng trên từng đơn hàng là thấp nhất
có thể
Nếu ngày hoàn thành đơn hàng > hạn giao hàng
7
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
Thời gian trễ hạn = ngày hoàn thành đơn hàng – hạn giao
hàng (ngày)
Nếu ngày hoàn thành đơn hàng <= hạn giao hàng
Thời gian trễ hạn = 0 (ngày)

Tổng thời gian trễ hạn = sum(thời gian trễ hạn trên từng đơn
hàng) (ngày)
1.2. Xây dựng mô hình
a. Mô hình cho dữ liệu, thông tin và tri thức: Được mô hình hóa
dưới dạng các đối tượng
- Phân xưởng: Mã phân xưởng, Loại phân xưởng, Năng suất
+ Mã phân xưởng: duy nhất cho một phân xưởng
+ Loại phân xưởng: phân theo chức năng của phân xưởng, được
quy định: 0  phân xưởng cắt; 1  phân xưởng ráp
- Đơn hàng: Mã đơn hàng, Số lượng, Hạn giao hàng
+ Mã đơn hàng: mã đơn hàng duy nhất cho mỗi đơn hàng
+ Số lượng: số lượng hàng hóa đã đặt
+ Hạn giao hàng: thời hạn hàng hóa phải giao đủ số lượng
b. Mô hình cho giả thiết
- Input: danh sách phân xưởng, danh sách đơn hàng
Bảng 1.2.1: Mô hình danh sách phân xưởng
Mã phân xưởng Loại phân xưởng Năng suất
(sản phẩm)
PX1 0 100
PX2 0 160
PX3 1 120
PX4 1 100
8
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
Bảng 1.2.2: Mô hình danh sách đơn hàng
Mã đơn hàng Số lượng
(sản phẩm)
Hạn giao
(Ngày thứ…)
DH1 1000 8

DH2 1200 13
DH3 950 17
DH4 800 15
DH5 1500 20
- Output: lịch trình cho tất cả phân xưởng để sản xuất cho tất cả
các đơn hàng.
c. Mô hình cho mục tiêu
- Lịch trình: Ngày, Phân xưởng, Ca, Đơn hàng, Số lượng
+ Ngày: ngày làm việc bắt đầu từ ngày bắt đầu lịch trình, ngày
bắt đầu lịch trình là ngày 1.
+ Phân xưởng: mã phân xưởng được phân công
+ Ca: 1, 2 hoặc 3 (Ca 1: buổi sáng, Ca 2: buổi chiều, Ca 3: tăng
ca)
+ Đơn hàng: mã đơn hàng sẽ sản xuất trong 1 ca của một phân
xưởng
+ Số lượng: số lượng sẽ sản xuất trong 1 ca của 1 phân xưởng
Bảng 1.2.3: Mô hình lịch trình sản xuất
Ngày Phân
xưởng
Ca Đơn hàng Số lượng
1 PX1 1 DH1 50
1 PX1 2 DH1 50
1 PX1 3 DH1 25
1 PX2 1 DH1 75
1 PX2 2 DH1 75
2 PX3 1 DH1 60
2 PX3 2 DH2 60
d. Mô hình cho điều kiện và các ràng buộc
- Thiết lập một danh sách tạm để kiểm tra các điều kiện ràng buộc
cho mỗi phân xưởng trong 1 ngày, bằng cách gán số lượng tối đa

có thể sản xuất của phân xưởng đó – năng suất tối đa:
Năng suất tối đa: Mã phân xưởng, Số lượng ca chính (ca 1,
ca 2), Số lượng tăng ca.
9
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
Bảng 1.2.4: Mô hình danh sách năng suất tối đa
Phân xưởng Số lượng
Ca 1
Số lượng
Ca 2
Số lượng
tăng ca
PX1 50 50 25
PX2 80 80 40
PX3 50 50 25
PX4 60 60 30
- Thiết lập danh sách số lần tăng ca cho mỗi phân xưởng để kiểm
tra số lần tăng ca tối đa trong tuần, 1 tuần được xác định trong
khung 7 ngày kể từ ngày bắt đầu lịch trình được tính bằng công
thức:
Tuần thứ = ngày / 7 (chia lấy phần nguyên)
Bảng 1.2.5: Mô hình danh sách số lần tăng ca trong tuần
Phân xưởng Số lần tăng ca còn lại
PX1 4
PX2 4
PX3 4
PX4 4
Khi có tăng ca cho 1 phân xưởng thì giảm số lần tăng ca còn
lại xuống một, nếu không còn lần tăng ca nào thì không cho
phép tăng ca trong tuần đó, của phân xưởng đó.

Sau khi kết thúc một tuần thì số lần tăng ca còn lại được trả về
số lần tăng ca tối đa
2. Thiết kế thuật giải
2.1. Lựa chọn phương pháp
- Quy trình sản xuất gồm hai công đoạn là cắt và ráp, trong đó ráp
phải thực hiện khi công đoạn cắt đã hoàn thành. Có thể thấy công
đoạn cắt phải kế thừa từ kết quả đã hoàn thành từ công đoạn cắt.
Vì thế ta có thể tách hai công đoạn ra riêng biệt để xử lý.
- Trước tiên là hoàn thành lịch trình cho công đoạn cắt sao cho
thỏa các điều kiện, ràng buộc.
- Sau đó dựa vào kết quả đã đạt được ở công đoạn cắt phân lịch
trình cho công đoạn ráp.
10
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
- Tổng thời gian sản xuất sẽ là thời gian kết thúc công đoạn ráp
cuối cùng trong lịch trình. Và thời gian giao hàng cho mỗi đơn
hàng là thời gian hoàn thành công đoạn ráp cuối cùng cho mặt
hàng cuối cùng của một đơn hàng.
- Có nhiều phương pháp có thể sử dụng để giải quyết vấn đề lập
lịch này. Từ vét cạn đến các phương pháp heuristic. Có một
phương pháp khá đơn giản để giải quyết vấn đề này là dựa vào
nguyên lý xếp thứ tự.
- Ta có thể chọn phương pháp xếp thứ tự để giải quyết lịch trình
cho tất cả phân xưởng cắt. Sau khi có được kết quả, ta sử dụng
kết quả đó để sắp xếp lịch trình cho các phân xưởng ráp.
2.2. Ý tưởng cho thuật giải
- Từ dữ liệu đầu vào ta lọc lấy những phân xưởng cắt (có loại phân
xưởng là “0”). Hình thành một lịch trình theo các nguyên tắc sắp
xếp thứ tự:
+ Đặt hàng trước làm trước (First come, first served - FCFS)

+ Giao hàng trước làm trước (Earliest Due Date - EDD)
+ Thời gian thực hiện ngắn nhất (số lượng ít nhất) làm trước
(Shortest Processing Time - SPT)
+ Thời gian dài nhất (số lượng nhiều nhất) làm trước (Longest
Processing Time - LPT)
- Ví dụ một dữ liệu đơn giản gồm 1 phân xưởng cắt, 1 phân xưởng
ráp năng suất cả hai phân xưởng bằng nhau là 200 sản phẩm mỗi
ngày (mỗi ca 100 sản phẩm), công ty làm việc cả 7 ngày trong
tuần và các đơn hàng như bảng sau:
Bảng 2.2.1: Dữ liệu đơn hàng
Mã đơn hàng Số lượng Số ca Hạn giao
DH1 1,000 10 7
DH2 600 6 11
DH3 400 4 9
DH4 1,200 12 18
DH5 800 8 14
DH6 2,000 20 24
TỔNG CỘNG 6,000 60
11
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
a. Sắp xếp thứ tự theo FCFS
- Sắp xếp theo nguyên tắc: thực hiện theo thứ tự các đơn hàng
- Theo thứ tự này ta lần lượt thực hiện các đơn hàng: 1, 2, 3, 4,
5, 6
- Kết quả sắp sếp như sau:
Bảng 2.2.2: Kết quả sắp xếp FCFS
Đơn hàng Số ca
(ca)
Thời hạn
(ngày)

Hoàn thành
(ngày thứ)
Số ngày trễ
(ngày)
DH1 10 7 5 0
DH2 6 11 8 0
DH3 4 9 10 1
DH4 12 18 16 0
DH5 8 14 20 6
DH6 20 24 30 6
TỔNG CỘNG 60 89 13
b. Sắp xếp thứ tự theo EDD
- Sắp xếp theo nguyên tắc: đơn hàng nào cần giao sớm sẽ làm
trước
- Theo thứ tự này ta lần lượt thực hiện các đơn hàng: 1, 3, 2, 5,
4, 6
- Kết quả sắp xếp như sau:
Bảng 2.2.3: Kết quả sắp xếp EDD
Đơn hàng Số ca
(ca)
Thời hạn
(ngày)
Hoàn thành
(ngày thứ)
Số ngày trễ
(ngày)
DH1 10 7 5 0
DH3 4 9 7 0
DH2 6 11 10 0
DH5 8 14 14 0

DH4 12 18 20 2
DH6 20 24 30 6
TỔNG CỘNG 60 86 8
c. Sắp xếp thứ tự theo SPT
- Sắp xếp theo nguyên tắc: đơn hàng nào ít sẽ ưu tiên làm trước
- Theo thứ tự này ta lần lượt thực hiện các đơn hàng: 3, 2, 5, 1,
4, 6
- Kết quả sắp xếp như sau:
12
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
Bảng 2.2.4: Kết quả sắp xếp SPT
Đơn hàng Số ca
(ca)
Thời hạn
(ngày)
Hoàn thành
(ngày thứ)
Số ngày trễ
(ngày)
DH3 4 9 2 0
DH2 6 11 5 0
DH5 8 14 9 0
DH1 10 7 14 7
DH4 12 18 20 2
DH6 20 24 30 6
TỔNG CỘNG 60 80 15
d. Sắp xếp thứ tự theo LPT
- Sắp xếp theo nguyên tắc: đơn hàng nào nhiều sẽ ưu tiên làm
trước
- Theo thứ tự này ta lần lượt thực hiện các đơn hàng: 6, 4, 1, 5,

2, 3
- Kết quả sắp xếp như sau:
Bảng 2.2.5: Kết quả sắp xếp LPT
Đơn hàng Số ca
(ca)
Thời hạn
(ngày)
Hoàn thành
(ngày thứ)
Số ngày trễ
(ngày)
DH6 20 24 10 0
DH4 12 18 16 0
DH1 10 7 21 14
DH5 8 14 25 11
DH2 6 11 28 17
DH3 4 24 30 6
TỔNG CỘNG 60 130 48
- Từ 4 kết quả sắp xếp ta so sánh các chỉ số tổng dòng thời gian và
tổng thời gian trễ hạn để tìm ra phương án tối ưu nhất cho thuật
giải.
Bảng 2.2.6: Bảng so sánh mức độ tối ưu
Loại sắp xếp Tổng dòng thời gian Tổng thời gian trễ
FCFS 89 13
EDD 86 8
SPT 80 15
LPT 130 48
13
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
- Ta dễ dàng nhận thấy kết quả sắp xếp theo LPT là không khả thi

vì tổng dòng thời gian và tổng thời gian trễ hạn rất cao.
- Nếu sắp xếp theo FCFS thì cũng chưa được tối ưu vì tổng thời
gian trễ hạn và tổng dòng thời gian vẫn còn cao hơn 2 thứ tự còn
lại.
- Sắp xếp theo EDD có tổng thời gian trễ là thấp nhất
- Sắp xếp theo SPT có tổng dòng thời gian là thấp nhất
- Tuy nhiên nếu xét cả hai chi số bằng cách tổng lại thì EDD tối ưu
hơn: EDD (86+8=94), SPT (80+15=95).
- Mặc khác mục tiêu đảm bảo thời hạn giao hàng cho khách hàng
được đặt lên hàng đầu.
- Do đó phương pháp sắp xếp tối ưu nhất ta chọn là sắp xếp theo
EDD (Earliest Due Date) – đơn hàng nào có hạn giao sớm hơn
thực hiện trước.
- Bên trên là trường hợp chỉ có một phân xưởng. Nếu phân cho
nhiều phân xưởng thì ta lần lượt phân từng đơn hàng cho từng
phân xưởng, trên từng ca. Nếu đơn hàng đã hết số lượng mà vẫn
còn phân xưởng chưa được phân thì ta lấy đơn hàng tiếp theo để
phân. Nếu phân hết cho các phân xưởng mà số lượng trong đơn
hàng vẫn còn thì ta tiếp tục phân cho ngày hôm sau.
- Cũng với ví dụ trên nhưng giả sử ta có hai phân xưởng có cùng
năng suất sản xuất là 100 sản phẩm mỗi ca,sử dụng phương pháp
sắp xếp EDD, ta có bảng lịch trình như sau:
Bảng 2.2.6: Bảng lịch trình sản xuất cho 2 phân xưởng cắt
Ngày Phân
xưởng
Ca Đơn hàng Số lượng
1 PX1 1 DH1 100
1 PX2 1 DH1 100
1 PX1 2 DH1 100
1 PX2 2 DH1 100

2 PX1 1 DH1 100
2 PX2 1 DH1 100
2 PX1 2 DH1 100
2 PX2 2 DH1 100
3 PX1 1 DH1 100
3 PX2 1 DH1 100
14
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
3 PX1 2 DH3 100
3 PX2 2 DH3 100
… … … … …
15 PX1 1 DH6 100
15 PX2 1 DH6 100
15 PX1 2 DH6 100
15 PX2 2 DH6 100
- Sau khi có kết quả lịch trình cho các phân xưởng cắt, ta dựa vào
đó để phân cho các phân xưởng ráp, lịch trình của phân xưởng
ráp sẽ bắt đầu chậm hơn các phân xưởng cắt ít nhất 1 ca làm việc.
- Kết quả phân cho 2 phân xưởng ráp có năng suất sản xuất mỗi ca
100 sản phẩm theo ví dụ trên và có lịch trình như bảng 2.2.6 như
sau:
Bảng 2.2.7: Bảng lịch trình sản xuất cho 2 phân xưởng ráp
Ngày Phân
xưởng
Ca Đơn hàng Số lượng
1 PX3 1 x x
1 PX4 1 x x
1 PX3 2 DH1 100
1 PX4 2 DH1 100
2 PX3 1 DH1 100

2 PX4 1 DH1 100
2 PX3 2 DH1 100
2 PX4 2 DH1 100
3 PX3 1 DH1 100
3 PX4 1 DH1 100
3 PX3 2 DH1 100
3 PX4 2 DH1 100
… … … … …
15 PX3 1 DH6 100
15 PX4 1 DH6 100
15 PX3 2 DH6 100
15 PX4 2 DH6 100
16 PX3 1 DH6 100
16 PX4 1 DH6 100
15
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
- Kết quả theo thời hạn giao hàng như sau:
Bảng 2.2.8: Bảng kết quả thời hạn giao hàng
Đơn hàng Số ca
(ca)
Thời hạn
(ngày)
Hoàn thành (ngày
thứ)
Số ngày trễ
(ngày)
DH1 10 7 0,5
(*)
+10/(2*2)
(**)

= 3 0
DH3 4 9 3+4/(2*2) = 4 0
DH2 6 11 4+6/(2*2) = 5,5 0
DH5 8 14 5,5+8/(2*2) = 7,5 0
DH4 12 18 7,5+12/(2*2) = 10,5 0
DH6 20 24 10,5+20/(2*2) = 15,5 0
TỔNG CỘNG 60 43,5 0
(*)
Kết quả hoàn thành dựa trên kết quả công đoạn ráp, công đoạn ráp
bắt đầu trễ hơn công đoạn cắt 1 ca tức 0,5 ngày
(**)
Có 2 phân xưởng, mỗi ngày 2 ca => tổng số ca mỗi ngày là 2*2
2.3. Mô tả cụ thể
- Trước hết dựa và dữ liệu đầu vào, ta sắp xếp thứ tự các đơn hàng
theo hạn giao hàng
- Chia dữ liệu phân xưởng thành hai danh sách theo loại phân
xưởng (cắt hoặc ráp)
- Phân công lịch trình cho các phân xưởng cắt bằng cách phân số
lượng của từng đơn hàng theo thứ tự đã sắp xếp và các phân
xưởng theo năng suất sản xuất trên từng ca, hết ca 1 đến ca 2
cũng tương tự như vậy, và hết ca 2 thì sang ca 1 ngày tiếp theo,…
đến khi nào hết đơn hàng thì thôi.
- Phân công lịch trình cho các phân xưởng rắp bằng cách lấy tổng
số lượng bán thành phẩm được tạo ra ở ca trước đó của các phân
16
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
xưởng ráp theo từng đơn hàng và phân cho các phân xưởng ráp
theo nguyên tắc tương tự như các phân xưởng cắt, nếu hết số
lượng bán thành phẩm thì thực hiện lại việc phân lịch trình cho ca
tiếp theo, nếu số lượng bán thành phẩm vẫn còn thì dồn vào ca

tiếp theo để phân và ưu tiên phân những bán thành phẩm còn
thừa từ ca trước đó trước.
- Thực hiện tăng ca: khi phân lịch trình ta tính toán trước thời gian
thực hiện bằng cách chia tổng số sản phẩm của đơn hàng cho
tổng năng suất sản xuất trên ngày của tất cả các phân xưởng
thuộc loại đang xử lý. Nếu kết quả nhận được (số ngày) trong hạn
giao hàng thì không cần tăng ca. Nếu kết quả nhận được vượt quá
hạn giao hàng thì cho tăng ca theo các điều kiện và ràng buộc đã
đưa ra.
- Tập hợp dữ liệu lịch trình và xuất kết quả.
2.4. Thuật giải
a. Bằng mã giả
DSPX: danh sách phân xưởng
DSDH: danh sách đơn hàng
Input: DSPX, DSDH
Output: LTSX (lịch trình sản xuất cho tất cả các phân xưởng)
Bước 1:
Sắp xếp thứ tự DSDH theo nguyên tắc EDD;
Tách DSPX thành:
DSPX1 (chứa các phân xưởng cắt, loại phân xưởng = “0”);
DSPX2 (chứa các phân xưởng ráp, loại phân xưởng = “1”);
Khởi tạo DSNS (danh sách năng xuất) ghi nhận năng suất tối đa
của tất cả các phân xưởng ở ca chính và tăng ca;
Khởi tạo DSTC (danh sách tăng ca) gán giá trị ở thuộc tính số
lần tăng ca còn lại là 4;
NXL (ngày xử lý) = 1;
CaXL (ca xử lý) = 1;
TNX (tổng năng suất) = sum(năng suất tất cả phân xưởng trong
DSPX1);
LTSX = rỗng;

i = 1;
TC = false;
Bước 2:
17
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
Lặp DHXL (đơn hàng xử lý) = đơn hàng đầu tiên đến đơn hàng
cuối cùng
Thực hiện
Nếu số lượng của DHXL / TNX > hạn giao của DHXL – NXL
Thì TC = true; Kết thúc
Lặp khi số lượng của DHXL > 0
Thực hiện
PXXL = DSPX1 thứ i trong DSNS;
Nếu số lượng của DHXL > năng suất ca CaXL của PXXL
Thì
Thêm LTSX (NXL, CaXL, DSPX1 thứ i, NS);
Số lượng DHXL = Số lượng DHXL - năng suất ca
CaXL của PXXL;
Tăng i lên 1;
Nếu i > số lượng phần tử trong DSPX1
Thì
i = 1;
Nếu CaXL = 1
Thì
CaXL = 2;
Ngược lại Nếu CaXL = 2 và TC = true và DSPX1
thứ i còn tăng ca được
CaXL = 3;
Ngược lại Nếu CaXL = 3 hoặc (CaXL = 2 và (TC =
false hoặc DSPX1 thứ i không còn tăng ca được))

CaXL = 1;
Tăng NXL lên 1;
Khôi phục là DSNS trở về ban đầu
Nếu NXL % 7 = 0 (chủ nhật) thì tăng NXL lên
1
Kết thúc
Kết thúc
Ngược lại
Thêm LTSX (NXL, CaXL, DSPX1 thứ i, số lượng của
DHXL);
Giảm năng xuất ca CaXL của PXXL xuống số lượng
của DHXL.
Số lượng DHXL = 0;
Kết thúc
Kết thúc lặp
Kết thúc lặp
Bước 3:
LTSX1 = LTSX;
18
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
NXL = 1;
CaXL = 2;
i = 1;
DSPC (danh sách phân công cho các phân xưởng cắt) = rỗng;
Lặp từ ca bắt đầu đến ca kết thúc của LTSX1
Thực hiện
DSPC = LTSX1 theo NXL và CaXL, nhóm theo DSDH;
Lặp khi DSPC khác rỗng
Thực hiện
Lấy 1 chi tiết (PC) trong DSPC;

Lặp khi số lượng của PC > 0
Thực hiện
Nếu số lượng của PC > năng suất DSPX2 thứ i
Thì
Thêm LTSX(NXL, CaXL, DH của PC, năng suất
của DSPX2 thứ i);
Số lượng PC = Số lượng PC - năng suất của
DSPX2 thứ i;
Tăng i lên 1;
Nếu i > số phần tử trong DSPX2
Thì
i = 1;
Nếu CaXL = 1
Thì
CaXL = 2;
Ngược lại nếu CaXL = 2 và DSPC khác rỗng và
DSPX2 thứ i còn tăng ca được
Thì
CaXL = 3;
Ngược lại nếu CaXL = 3 hoặc DSPX2 thứ i
không còn tăng ca được
CaXL = 1;
Tăng NXL lên 1;
Nếu NXL % 7 = 0 (chủ nhật) thì tăng NXL
lên 1;
Kết thúc
Kết thúc
Ngược lại
Thêm LTSX(NXL, CaXL, DH của PC, số lượng
của PC);

Giảm năng suất của phân xưởng được phân tại ca
được phân xuống số lượng đã phân;
Số lượng PC = 0;
19
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
Kết thúc
Kết thúc lặp
Kết thúc lặp
Kết thúc lặp
Bước 4:
Trả kết quả lịch trình là danh sách LTSX;
b. Bằng ngôn ngữ lập trình (C#).
private List<LichTrinh> LapLich(List<PhanXuong> DSPX, List<DonHang>
DSDH)
{
//sắp xếp danh sách đơn hàng theo EDD
DSDH.Sort(delegate(DonHang dh1, DonHang dh2) { return
dh1.HanGiao.CompareTo(dh2.HanGiao); });
//Lấy danh sách phân xưởng cắt
List<PhanXuong> DSPX1 = DSPX.FindAll(delegate(PhanXuong px) {
return px.LoaiPX == 0; });
//Lấy danh sách phân xưởng ráp
List<PhanXuong> DSPX2 = DSPX.FindAll(delegate(PhanXuong px) {
return px.LoaiPX == 1; });
//Khởi tạo danh sách năng suất
List<NangSuat> DSNS = KhoiTaoDSNS(DSPX);
//Khởi tạo danh sách số lần tăng ca tối đa/tuần của các phân xưởng
List<TangCa> DSTC = KhoiTaoDSTC(DSPX);
int NXL = 1; //Ngày xử lý
int CaXL = 1; //Ca xử lý

int TNX = 0; //Tổng năng suất
foreach (PhanXuong px in DSPX1)
{
TNX += px.NangSuat;
}
List<LichTrinh> LTSX = new List<LichTrinh>();
int i = 0;
bool TC = false; //Kiểm tra có tăng ca
//Lập lịch trình sản xuất cho các phân xưởng cắt
foreach (DonHang DHXL in DSDH)
{
if (DHXL.SoLuong / TNX > DHXL.HanGiao - NXL)
{
TC = true;
}
while (DHXL.SoLuong > 0)
{
PhanXuong PXXL = DSPX1[i];
int NSCaXL = NangSuatCaXL(DSNS, PXXL.MaPX, CaXL);
if (DHXL.SoLuong > NSCaXL)
{
LTSX.Add(new LichTrinh() { Ngay = NXL, Ca = CaXL, MaPX
= DSPX1[i].MaPX, MaDH = DHXL.MaDH, SoLuong =
NSCaXL });
DHXL.SoLuong -= NSCaXL;
i++;
if (i >= DSPX1.Count)
{
20
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên

i = 0;
if (CaXL == 1)
{
CaXL = 2;
}
else if (CaXL == 2 && TC && ConTangCaDuoc(DSTC,
PXXL.MaPX))
{
CaXL = 3;
}
else if (CaXL == 3 || (CaXL == 2 && (!TC || !
ConTangCaDuoc(DSTC, PXXL.MaPX))))
{
CaXL = 1;
NXL++;
DSNS = KhoiTaoDSNS(DSPX);
if (NXL % 7 == 0)
{
NXL++;
DSTC = KhoiTaoDSTC(DSPX);
}
}
}
}
else
{
LTSX.Add(new LichTrinh() { Ngay = NXL, Ca = CaXL, MaPX
= DSPX1[i].MaPX, MaDH = DHXL.MaDH, SoLuong =
DHXL.SoLuong });
TruNSCa(DSNS, PXXL.MaPX, CaXL, DHXL.SoLuong);

DHXL.SoLuong = 0;
}
}
}
//Lập lịch trình sản xuất cho phân xưởng ráp
List<LichTrinh> LTSX1 = new List<LichTrinh>();
foreach (LichTrinh lt in LTSX)
{
LTSX1.Add(new LichTrinh() { Ngay = lt.Ngay, Ca = lt.Ca, MaPX
= lt.MaPX, MaDH = lt.MaDH, SoLuong = lt.SoLuong });
}
int NKTCat = NXL; //Ngày kết thúc công đoạn cắt
NXL = 1;
CaXL = 2;
int CaCat = 1, NgayCat = 1; //Ca cắt xử lý, Ngày cắt xử lý
i = 0;
List<DonHang> DSPC = new List<DonHang>();
while (true)
{
DSPC = LayDSPC(DSPC, LTSX1, NgayCat, CaCat);
foreach (DonHang PCXL in DSPC)
{
while (PCXL.SoLuong > 0)
{
PhanXuong PXXL = DSPX2[i];
int NSCaXL = NangSuatCaXL(DSNS, PXXL.MaPX, CaXL);
if (PCXL.SoLuong > NSCaXL)
{
21
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên

LTSX.Add(new LichTrinh() { Ngay = NXL, Ca = CaXL,
MaPX = DSPX2[i].MaPX, MaDH = PCXL.MaDH, SoLuong =
NSCaXL });
PCXL.SoLuong -= NSCaXL;
i++;
if (i >= DSPX2.Count)
{
i = 0;
if (CaXL == 1)
{
CaXL = 2;
}
else if (CaXL == 2 && TC &&
ConTangCaDuoc(DSTC, PXXL.MaPX))
{
CaXL = 3;
}
else if (CaXL == 3 || (CaXL == 2 && (!TC || !
ConTangCaDuoc(DSTC, PXXL.MaPX))))
{
CaXL = 1;
NXL++;
DSNS = KhoiTaoDSNS(DSPX);
if (NXL % 7 == 0)
{
NXL++;
DSTC = KhoiTaoDSTC(DSPX);
}
}
}

}
else
{
LTSX.Add(new LichTrinh() { Ngay = NXL, Ca = CaXL,
MaPX = DSPX2[i].MaPX, MaDH = PCXL.MaDH, SoLuong =
PCXL.SoLuong });
TruNSCa(DSNS, PXXL.MaPX, CaXL, PCXL.SoLuong);
PCXL.SoLuong = 0;
}
}
}
CaCat++;
if (CaCat > 3)
{
CaCat = 1;
NgayCat++;
if (NgayCat % 7 == 0) NgayCat++;
}
if (NXL <= NgayCat && CaXL <= CaCat)
{
if (CaCat < 3)
{
NXL = NgayCat;
CaXL = CaCat + 1;
}
else
{
NXL = NgayCat + 1;
CaXL = 1;
}

}
22
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
if (NgayCat > NKTCat) break;
}
return LTSX;
}
Những hàm liên quan trong tính toán
private List<NangSuat> TruNSCa(List<NangSuat> DSNS, string MaPX, int
CaXL, int SoLuong)
{
NangSuat ns = DSNS.Find(delegate(NangSuat n) { return n.MaPX ==
MaPX; });
if (CaXL == 1) ns.SLCa1 = ns.SLCa1 - SoLuong;
else if (CaXL == 2) ns.SLCa2 = ns.SLCa2 - SoLuong;
else ns.SLTCa = ns.SLTCa - SoLuong;
return DSNS;
}
private int NangSuatCaXL(List<NangSuat> DSNS, string MaPX, int CaXL)
{
NangSuat ns = DSNS.Find(delegate(NangSuat n) { return n.MaPX ==
MaPX; });
if (CaXL == 1) return ns.SLCa1;
else if (CaXL == 2) return ns.SLCa2;
else return ns.SLTCa;
}
private List<TangCa> KhoiTaoDSTC(List<PhanXuong> DSPX)
{
List<TangCa> DSTC = new List<TangCa>();
foreach (PhanXuong px in DSPX)

DSTC.Add(new TangCa() { MaPX = px.MaPX, ConLai = 4 });
return DSTC;
}
private bool ConTangCaDuoc(List<TangCa> DSTC, string MaPX)
{
TangCa tc = DSTC.Find(delegate(TangCa t){return t.MaPX == MaPX;});
return tc.ConLai > 0;
}
private List<DonHang> LayDSPC(List<DonHang> DSPC, List<LichTrinh>
LTSX, int Ngay, int Ca)
{
List<LichTrinh> LTTheoCa = LTSX.FindAll(delegate(LichTrinh lt) {
return lt.Ngay == Ngay && lt.Ca == Ca; });
bool isAdd = true;
foreach (LichTrinh lt in LTTheoCa)
{
isAdd = true;
foreach (DonHang dh in DSPC)
{
if (dh.MaDH == lt.MaDH)
{
dh.SoLuong += lt.SoLuong;
isAdd = false;
break;
}
23
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
}
if (isAdd)
{

DSPC.Add(new DonHang() { MaDH = lt.MaDH, SoLuong =
lt.SoLuong });
}
for (int i = DSPC.Count - 1; i >= 0; i )
{
if (DSPC[i].SoLuong <= 0) DSPC.RemoveAt(i);
}
}
return DSPC;
}
3. Chứng minh tính hiệu quả
- Phương pháp xếp thứ tự là một phương pháp đơn giản cho vấn đề lập
lịch, cụ thể là lịch trình sản xuất.
- Ta có thể nhận thấy những đơn hàng có thời hạn giao hàng càng gần thì
càng phải được hoàn thành sớm. Do đó sắp xếp theo thứ tự đơn hàng
nào hạn giao hàng gần nhất thì làm trước là một cách thức hiệu quả để
giải quyết bài toán này.
- Phương pháp xếp thứ tự làm đơn giản hóa bài toán phân công n công
việc cho m đối tượng sao cho tối ưu nhất. Ở đây cụ thể là phân công n
đơn hàng cho m phân xưởng, chỉ số tối ưu được xác định dựa vào thời
hạn giao hàng, càng ít trễ, càng tối ưu.
- Tuy nhiên, chỉ một số bài toán cụ thể mới có thể áp dụng được phương
pháp này và phải kết hợp nhiều yếu tố khác cũng như xác định chính xác
được cách thức sắp xếp.
4. Kiểm chứng thực nghiệm
- Sau khi cài đặt và thử nghiệm thuật giải, có thể thấy được thuật giải khá
hiệu quả, giải quyết vấn đề một cách nhanh chóng, đưa ra được một lịch
trình chi tiết gần như tối ưu.
- Đặc biệt là lịch trình của các phân xưởng cắt, có thể được xem là tối ưu
vì tận dụng được hết năng suất của các phân xưởng.

- Thuật giải đáp ứng tốt mục tiêu của vấn đề là giảm thiếu thời gian chậm
trễ của các đơn hàng.
- Từ dữ liệu tính toán sau khi cài đặt thuật giải ta có thể rút ra được các
lịch trình đa dạng: theo ngày, theo phân xưởng,…
24
Vấn đề: lập lịch trình sản xuất CH1301091 – Đoàn Văn Huyên
- Từ cài đặt thử nghiệm ta thu được một số các lịch trình:
Bảng 4.1: Lịch trình sản xuất cho ngày thứ nhất
Ngày Ca Phân xưởng Đơn hàng Số lượng
1 1 PX1 DH1 60
1 1 PX2 DH1 50
1 1 PX3 DH1 75
1 1 PX4 DH1 90
1 2 PX1 DH1 60
1 2 PX2 DH1 50
1 2 PX3 DH1 75
1 2 PX4 DH1 90
1 2 PX5 DH1 75
1 2 PX6 DH1 50
1 2 PX7 DH1 50
1 2 PX8 DH1 60
1 3 PX5 DH1 37
1 3 PX6 DH1 3
1 3 PX6 DH1 22
1 3 PX7 DH1 25
1 3 PX8 DH1 30
Bảng 4.2: Lịch trình sản xuất cho phân xưởng một
Ngày Ca Phân xưởng Đơn hàng Số lượng
1 1 PX1 DH1 60
1 2 PX1 DH1 60

2 1 PX1 DH1 60
2 2 PX1 DH1 60
3 1 PX1 DH2 60
3 2 PX1 DH2 60
4 1 PX1 DH2 60
4 2 PX1 DH4 60
5 1 PX1 DH4 60
5 2 PX1 DH5 60
6 1 PX1 DH5 60
… … …. … …
25