Ứng dụng chiến lược vét cạn để tối ưu cân bằng dây chuyền may công nghiệp

Tạp chí Khoa học và Công nghệ 141 (2020) 034-041 
34 
Ứng dụng chiến lược vét cạn để tối ưu cân bằng dây chuyền 
may công nghiệp 
Application of Exhaustive Search for Optimization Assembly Line Balancing in Garment Industry 
Đinh Mai Hương1,2*, Trương Văn Long1, Đỗ Phan Thuận1, Phan Thanh Thảo1, 
 Nguyễn Đức Nghĩa1 
1 Trường Đại học Bách Khoa Hà Nội - Số 1, Đại Cồ Việt, Hai Bà Trưng, Hà Nội 
2 Trường Đại học Công nghiệp Hà Nội - Số 298, đường Cầu Diễn, Bắc Từ Liêm, Hà Nội 
Đến Tòa soạn: 48-3-2019; chấp nhận đăng: 20-03-2020 
Tóm tắt 
Cân bằng phụ tải dây chuyền gọi tắt là cân bằng chuyền may là một nhiệm vụ quan trọng trong ngành sản 
xuất may công nghiệp nhằm nâng cao năng suất, giảm thiểu các chi phí sản xuất. Một số nghiên cứu đã 
được tiến hành để giải bài toán cân bằng chuyền may với các mục tiêu khác nhau. Đã có nhiều tiến bộ trong 
các phương pháp gần đúng để giải quyết vấn đề cân bằng chuyền may. Trong các giải thuật tối ưu, chiến 
lược vét cạn là phương pháp tìm nghiệm thường được áp dụng trên cơ sở xem xét tất cả các phương án để 
tìm ra nghiệm tốt nhất. Ưu điểm lớn nhất của phương pháp vét cạn là luôn tìm ra nghiệm chính xác. Bài báo 
này trình bày kết quả nghiên cứu tối ưu cân bằng chuyền may khi cho trước công suất của dây chuyền với 
hàm mục tiêu là tối thiểu số lượng công nhân tham gia sản xuất để dây chuyền đạt hiệu quả tổ chức cao. 
Trên cơ sở nghiên cứu điều kiện thực tế của dây chuyền may công nghiệp, nhóm tác giả đã mô tả các ràng 
buộc về trình tự thực hiện, thiết bị và thời gian thực hiện. Bài báo đã đề xuất thuật toán trên cơ sở ứng dụng 
chiến lược vét cạn để tìm giải pháp tối ưu cho mục tiêu đã nêu. Thuật toán đã được chạy thử nghiệm trên bộ 
dữ liệu thực tế liên quan đến sản xuất sản phẩm Polo-Shirt tại nhà máy may Đồng Văn thuộc Tổng công ty 
Dệt May Hà Nội. Các kết quả nghiên cứu lý thuyết và thực nghiệm thu được góp phần xây dựng cơ sở khoa 
học để giải quyết vấn đề tối ưu cân bằng chuyền may công nghiệp. 
Từ khóa: Cân bằng chuyền may, kỹ thuật cân bằng, đồ thị, vét cạn. 
Abstract 
Assembly line balancing (ALB) is an important task for the garment industry to improve productivity and 
minimize production costs. Several studies on ALB have been conducted with different objectives. There has 
been much progress in approximate methods to solve the problem of ALB. In the optimal algorithms, the 
exhaustive search is the method of finding a test that is often applied on the basis of considering all options 
to find the best solution. The biggest advantage of the exhaustive search method is always finding the exact 
solution. This paper presents the optimal research results of ALB when giving the capacity of the line with 
the objective function of minimizing the number of workers involved in production so that the line can 
achieve high equilibrium efficiency. Based on the study of the actual conditions of the industrial sewing lines, 
the constraints on the order of execution, equipment and implementation time are described. The article has 
proposed an algorithm on the basis of exhaustive search applications to find the optimal solution for the 
stated goal. The algorithm was run and tested on the actual data set related to the production of Polo-Shirt 
products at Dong Van Garment Factory, Ha Noi Textile & Garment Joint Stock Corporation. The results of 
theoretical and empirical research have contributed to building a scientific basis to solve the problem of the 
optimal balance of the industrial sewing lines. 
Keywords: Asembly line balancing, balancing techniques, graph, exhaustive search. 
1. Đặt vấn đề* 
Sản xuất theo dây chuyền là một phương pháp 
tổ chức thực hiện các công việc trong sản xuất hàng 
loạt. Mỗi công việc hay còn gọi là các nguyên công 
công nghệ (NCCN) cần có một thời gian xử lý và một 
* Địa chỉ liên hệ: Tel.: (+84)947537677 
Email: huongdinhmai@gmail.com 
tập hợp các mối quan hệ ưu tiên để xác định trình tự 
của nguyên công. Nguyên công sản xuất (NCSX) gồm 
một số NCCN và được bố trí cho một chuỗi các vị trí 
làm việc trên dây chuyền, đảm bảo ràng buộc trình tự 
công nghệ được thỏa mãn. Vấn đề cân bằng phụ tải 
dây chuyền gọi tắt là cân bằng chuyền may là vấn đề 
phân phối thời gian cho các vị trí làm việc được đồng 
đều để dây chuyền đạt hiệu quả cao nhất [1], [2]. 
Tạp chí Khoa học và Công nghệ 141 (2020) 034-041 
35 
Vấn đề cơ bản của cân bằng chuyền với các mục 
tiêu khác nhau được phân thành 4 dạng. Dạng 1 được 
xây dựng nhằm tối thiểu số lượng công nhân khi cho 
trước nhịp dây chuyền, bài toán này tương ứng với 
việc thiết kế mới dây chuyền may. Trong dạng 2, cho 
trước số lượng công nhân, tối ưu nhịp dây chuyền. 
Dạng 3 liên quan đến tối đa hiệu quả dây chuyền khi 
đồng thời xem xét mối tương quan của số lượng công 
nhân và nhịp dây chuyền. Còn dạng 4 xem xét vấn đề 
khả thi cân bằng chuyền khi cố định cả số lượng công 
nhân và nhịp dây chuyền [2], [3]. 
Một số công trình nghiên cứu vấn đề cân bằng 
chuyền may dưới dạng bài toán phức tạp khi tổ hợp 
công việc lớn để áp dụng thuật toán giải gần đúng. 
Tác giả Santosh và cộng sự áp dụng phương pháp 
Rank Position Weight (RPW) với số lượng công nhân 
cho trước để tối ưu nhịp dây chuyền [4]. Tác giả 
Vrittika áp dụng ba phương pháp: Rank Position 
Weight; Largest Set Rul; Kilbridge và Wester 
Column với mục tiêu tối ưu nhịp dây chuyền khi cho 
trước số lượng công nhân, cả ba phương pháp cho kết 
quả khác biệt rất nhỏ [5]. Tác giả Eryuruk áp dụng 
hai phương pháp: Largest Set Rule và Probabilistic 
Line Balancing với nhịp dây chuyền cho trước để tối 
ưu số lượng công nhân, kết quả chỉ ra phương pháp 
Probabilistic Line Balancing cho phép phân chia công 
việc chính xác hơn nhưng số lượng công nhân nhiều 
hơn, phương pháp Largest Set Rule áp dụng dễ dàng 
và cho hiệu quả dây chuyền cao hơn [6]. Tác giả 
Jayakumar và cộng sự áp dụng phương pháp RPW 
với mục tiêu nâng cao hiệu quả dây chuyền [7]. Tác 
giả Chen và cộng sự đã sử dụng nhóm thuật toán di 
truyền để giải quyết vấn đề cân bằng dây chuyền với 
mục tiêu tối thiểu số lượng công nhân [8]. 
 Có rất ít công trình quan tâm đến vấn đề cân 
bằng dây chuyền trong thực tế như cho phép kết hợp 
các loại thiết bị đặc biệt cần vốn đầu tư lớn, thời gian 
sử dụng cho sản xuất ngắn. Phần lớn là nghiên cứu 
trường hợp thời gian của các NCCN nhỏ hơn nhịp dây 
chuyền, mỗi NCSX chỉ cho phép có một loại thiết bị, 
phương pháp áp dụng thường là gần đúng, kết quả 
tìm được có thể là tối ưu cục bộ. Cân bằng chuyền 
may bằng phương pháp thủ công sẽ khó để cho kết 
quả tối ưu, tốn rất nhiều thời gian và công sức, do vậy 
việc thiết lập một phần mềm giải quyết các bài toán 
cân bằng dây chuyền may khi xem xét các điều kiện 
thực tế sản xuất là cần thiết. 
Mục đích của nghiên cứu này là tối ưu cân bằng 
chuyền may công nghiệp trong điều kiện thực tế khi 
cho trước công suất của dây chuyền được xác định là 
số lượng sản phẩm sản xuất trong một ca làm việc. 
Thuật toán cân bằng chuyền được xây dựng trên cơ 
sở ứng dụng chiến lược vét cạn để tìm giải pháp tối 
ưu toàn cục. Thuật toán được chạy thử nghiệm trên 
bộ dữ liệu thực tế của nhà máy may Đồng Văn. Giả 
định của bài toán là năng lực và khả năng làm việc 
của công nhân là như nhau, không xét đến ảnh hưởng 
của bậc kỹ thuật của công nhân. 
2. Đối tượng và phương pháp nghiên cứu 
2.1. Đối tượng nghiên cứu: 
2.1.1. Dây chuyền may thực nghiệm 
Dây chuyền may sản phẩm dệt kim tại nhà máy 
may Đồng Văn, Tổng công ty Dệt May Hà Nội. Đây 
là sản phẩm truyền thống, điển hình của Tổng công ty 
với tỷ trọng sản xuất lớn. Hình thức tổ chức dây 
chuyền dạng liên hợp không chia nhóm, các thiết bị 
được bố trí thành hai hàng ngang, hình thức cung cấp 
bán thành phẩm theo tập. Dây chyền có nhịp tự do, 
mức độ dao động nhịp làm việc của dây chuyền ∆R = 
± (10% x R), Rmin = 0.9R; Rmax = 1.1R 
Thiết bị của dây chuyền được chia thành ba 
nhóm: Nhóm 1 gồm các máy may thông dụng, nhóm 
2 gồm các máy chuyên dùng, nhóm 3 là các công việc 
thủ công. Mỗi công nhân sử dụng không quá 2 loại 
thiết bị theo yêu cầu: Các thiết bị nhóm 1 không ghép 
với các thiết bị trong cùng nhóm và không ghép với 
nhóm 2. 
Thời gian định mức làm việc một ca của dây 
chuyền là Tlvca = 8 giờ (288000 giây), công suất thiết 
kế sản xuất sản phẩm Polo-Shirt cho mỗi dây chuyền 
là P = 400-500 (sản phẩm/ca). 
Mỗi NCSX không quá ba công nhân thực hiện. 
Mỗi công nhân phải hoàn thành công việc trong mức 
thời gian lao động cho phép có độ sai lệch không quá 
10% so với nhịp của dây chuyền. 
2.1.2. Sản phẩm thực nghiệm. 
Sản phẩm Polo-Shirt nam ngắn tay của mã hàng 
UM0495, đây là sản phẩm phổ biến trong nhóm sản 
phẩm quần áo dệt kim, hình dáng sản phẩm được 
minh họa trong hình 1, bảng quy trình công nghệ 
được lấy từ dữ liệu của nhà máy May Đồng Văn được 
minh họa trong bảng 1 [10]. 
Hình 1. Hình dáng áo Polo-Shirt [10] 
2.2. Phương pháp nghiên cứu 
2.2.1. Nghiên cứu xây dựng bài toán cân bằng chuyền 
 Gọi ti là thời gian để hoàn thành NCCN thứ i, Tsp 
là thời gian định mức may một sản phẩm theo bảng 
quy trình công nghệ. Tsp được xác định như sau: 
Tạp chí Khoa học và Công nghệ 141 (2020) 034-041 
36 
 (s) (1) 
Nhịp dây chuyền R(s) là thời gian trung bình mà 
dây chuyền may sản xuất một sản phẩm: 
 (2) 
Hiệu quả dây chuyền (LE) được xác định như 
sau: 
 (3) 
Trong đó: Nsx là số công nhân tham gia sản xuất. 
Để dây chuyền đạt hiệu quả dây chuyền cao khi cho 
trước công suất thì phải tối thiểu số lượng công nhân 
Nsx, để dây chuyền hoạt động nhịp nhàng thì số lượng 
NCSX có nhịp riêng nằm trong khoảng giới hạn nhịp 
là nhiều nhất. 
Bảng 1. Bảng quy trình công nghệ may áo Polo-Shirt 
TT 
Nguyên công 
công nghệ 
Tên 
thiết bị 
Nhóm 
thiết bị 
Thời gian 
ti (giây) 
1 Chần gấu áo TT MC2K 1 32 
2 May nẹp lệch MB1K 1 56 
3 Mí nẹp MB1K 1 128 
4 Ghim cụm mác MB1K 1 16 
5 Chần gấu áo TS MC2K 1 32 
6 May vai MX2K 1 37 
7 Chần vai MC1K 1 32 
8 May sống cổ MB1K 1 56 
9 Sửa sống cổ TC 3 19 
10 Mí sống cổ dưới MB1K 1 56 
11 May 2 đầu lá cổ MB1K 1 30 
12 Mí 2 cạnh cổ MB1K 1 30 
13 Là lá cổ BL 3 60 
14 May cặp ba lá cổ MB1K 1 96 
15 
Sửa cạnh trên 
chân cổ, 2 đầu cổ 
TC 3 23 
16 Mí chân cổ trên MB1K 1 46 
17 Sửa chân cổ dưới TC 3 19 
18 Ghim đầu chân cổ MB1K 1 46 
19 May tra cổ MX2K 1 63 
20 Mí chân cổ MB1K 1 63 
21 Tra tay MX2K 1 68 
22 
Chần đường tra 
tay 
MC1K 1 68 
23 
May sườn, bụng 
tay, chân nẹp 
MX2K 1 120 
24 May tà MB1K 1 96 
25 Chần 2 gấu tay MC2K 1 68 
26 Di 2 cửa tay MB1K 1 21 
27 Di bọ tà MDB 2 21 
28 Di bọ chân nẹp MDB 2 21 
29 Thùa khuyết MTK 2 32 
30 Đính cúc MDC 2 32 
 Tổng thời gian (giây) 1487 
Bài toán được phát biểu như sau: 
- Mục tiêu: Tối thiểu số lượng công nhân, Nsx
→Min 
- Điều kiện ràng buộc: 
+ Không vi phạm trình tự công nghệ thực hiện 
khi ghép các NCCN thành NCSX. 
+ Mỗi NCSX có tối đa 3 công nhân: Ncj ≤ 3 
+ Mức thời gian lao động của mỗi công nhân 
thuộc khoảng giới hạn nhịp [Rmin, Rmax] 
+ Mỗi công nhân sử dụng tối đa 2 loại thiết bị 
theo điều kiện: Các thiết bị nhóm 1 không ghép với 
các thiết bị trong cùng nhóm 1 và không ghép với 
nhóm 2. 
Nẹp TT TS Nhãn SD Lá cổ Chân cổ Tay
Chần gấu áo TT May sống cổ
May nẹp lệch Chần gấu áo TS Xén sửa sống cổ
Mí nẹp Mí sống cổ
May 2 vai May 2 đầu lá cổ
Chần vai Mí 2 cạnh cổ
Là lá cổ
May cặp ba lá cổ
Sửa cạnh trên chân cổ
Mí cạnh trên chân cổ
Sửa cạnh dưới chân cổ
Ghim 2 đầu chân cổ
Tra cổ
Mí chân cổ
Tra tay Mác
Chần đường tra tay
Gim cụm mác
May bụng tay+sườn+VS nẹp
May tà
Chần gấu tay
Di cửa tay
Di bọ tà
Di bọ nẹp
Thùa khuyết
Đính cúc
 Kết thúc
1
2
3
5
6
7
18
19
20
21
22
23
26
27
28
30
29
24
25
8
9
10
11
12
13
14
15
16
17
4
Hình 2. Sơ đồ phân tích quy trình công nghệ may sản 
phẩm áo Polo-Shirt 
2.2.2. Phương pháp xây dựng sơ đồ phân tích quy 
trình công nghệ và sơ đồ ưu tiên công nghệ 
Tạp chí Khoa học và Công nghệ 141 (2020) 034-041 
37 
Sơ đồ phân tích quy trình công nghệ: 
Sơ đồ phân tích quy trình công nghệ dạng tóm tắt 
thể hiện các thông tin về nội dung và trình tự gia công 
các NCCN được minh họa trong hình 2. 
Phương pháp xây dựng sơ đồ ưu tiên công 
nghệ: 
 Áp dụng lý thuyết về đồ thị để biểu diễn trực 
quan quy trình gia công sản phẩm may được gọi là sơ 
đồ ưu tiên công nghệ. Đồ thị là một tập các đối tượng 
gồm các đỉnh (nút) nối với nhau bởi các cạnh (cung), 
cạnh có thể có hướng hoặc vô hướng [9]. 
Một số NCCN có thể thay đổi trình tự gia công 
nhưng vẫn đảm bảo yêu cầu công nghệ, như vậy sẽ 
tạo ra một quy trình mới mà sơ đồ phân tích quy trình 
công nghệ không thể hiện được. Các NCCN có thể 
thay đổi thứ tự cho nhau được biểu diễn ở 2 nhánh 
song song. Ví dụ NCCN số 24 và số 25 có thể thay 
đổi thứ tự thực hiện cho nhau, NCCN số 27 và 28 có 
thể đổi thứ tự thực hiện cho nhau mà không ảnh 
hưởng đến hành trình công nghệ. Khi chuyển sang sơ 
đồ ưu tiên công nghệ đỉnh 24 và 25, đỉnh 27 và 28 
được biểu diễn ở 2 nhánh song song trong sơ đồ ưu 
tiên công nghệ hình 3, mô hình này được giải thích 
như sau NCCN 23 thực hiện xong sẽ chuyển sang 
NCCN 24 hoặc 25, sau khi thực hiện xong NCCN 24 
và 25 thì mới chuyển sang NCCN 26, tương tự NCCN 
26 thực hiện xong sẽ chuyển sang NCCN 27 hoặc 28, 
sau khi thực hiện xong NCCN 27 và 28 thì mới 
chuyển sang NCCN 29. 
2.2.3. Tính toán các thông số của dây chuyền 
Gọi tsxj là thời gian của NCSX j, ta có: 
 (4) 
Số công nhân tính toán của mỗi NCSXj là Ntj: 
 (5) 
Gọi Ncj là số công nhân chọn theo nguyên tắc làm 
tròn, nhịp riêng của mỗi NCSX thứ j là Rj, được xác 
định như sau: 
 (6) 
Gọi k là số NCSX được tạo thành thì tổng số công 
nhân sản xuất (Nsx) là: 
 (7) 
Gọi số NCSX thỏa mãn điều kiện Rmin ≤ Rj ≤ Rmax 
là k1, tỷ lệ NCSX thỏa mãn điều kiện nhịp H1 được 
xác định theo công thức sau: 
 (8) 
2.2.4. Phương pháp phối hợp các nguyên công công 
nghệ thành nguyên công sản xuất. 
Phối hợp các NCCN thành NCSX phải đảm bảo 
tính trình tự công nghệ để đường đi của bán thành 
phẩm là thẳng dòng và ngắn nhất. Có thể ghép các 
đỉnh của cùng một nhánh gia công, ví dụ ghép NCCN 
số 1 với 2, là các nguyên công nằm trên cùng nhánh, 
có đường đi từ 1 đến 2. Có thể theo nguyên tắc song 
song tức là ghép các đỉnh trên các nhánh khác nhau 
nhưng không ảnh hưởng đến tính trình tự công nghệ, 
ví dụ ghép NCCN số 1 với 8 là 2 NCCN khác nhánh. 
Bán thành phẩm không được vận chuyển qua lại 
giữa các NCSX, ví dụ trong hình 4 minh họa NCSX1 
gồm NCCN số 1, 2, 5 và 6, NCSX2 gồm NCCN số 3 
và 7. Đường đi của các nguyên công theo sơ đồ ưu 
tiên hình 3 là 1→2→3→6→7, trường hợp này đường 
đi của vật liệu di chuyển qua lại giữa NCSX1 và 
NCSX2, do vậy không đảm bảo tính trình tự công 
nghệ. 
1
2
3
5
6
7
18
19
20
21
22
23
26
27 28
30
29
24 25
8
9
10
11
12
13
14
15
16
17
4
Hình 3. Sơ đồ ưu tiên công nghệ 
Hình 4. Đường đi của bán thành phẩm di chuyển qua 
lại giữa các NCSX. 
Tạp chí Khoa học và Công nghệ 141 (2020) 034-041 
38 
2.2.5. Lựa chọn thuật toán tối ưu cân bằng chuyền 
Vét cạn là chiến lược thiết kế giải thuật, là 
phương pháp tìm nghiệm của bài toán tối ưu bằng 
cách xem xét tất cả các phương án có thể để tìm ra 
nghiệm tốt nhất. Ưu điểm lớn nhất của phương pháp 
vét cạn là luôn tìm ra nghiệm chính xác. Đối với bài 
toán cân bằng chuyền may sản phẩm áo Polo-Shirt, số 
lượng các đỉnh là 30 không quá lớn, sơ đồ ưu tiên là 
một dạng đồ thị có hướng, không có chu trình, vì vậy, 
có thể áp dụng phương pháp vét cạn để giải bài toán 
này. 
3. Kết quả nghiên cứu 
3.1. Thuật toán tối ưu cân bằng chuyền 
Bài toán cân bằng dây chuyền may trong nghiên 
cứu này được xây dựng với mục tiêu tối thiểu số 
lượng công nhân tham gia sản xuất trên dây chuyền. 
Dữ liệu đầu vào gồm: Trình tự công nghệ của 
các NCSX được tham số hóa bằng danh sách cạnh [9], 
thời gian, tên máy, loại máy của các NCCN. Bằng 
thuật toán áp dụng chiến lược vét cạn với các điều 
kiện ràng buộc, kết quả thu được là bảng NCSX và 
các chỉ số hiệu quả dây chuyền, tỷ lệ phần trăm NCSX 
thỏa mãn điều kiện nhịp. Thuật toán cân bằng chyền 
áp dụng chiến lược vét cạn như sau: 
 Giả thiết Tập NCSX cần tìm có dạng (NCSX1, 
NCSX2,  NCSXk), áp dụng chiến lược vét cạn thiết 
kế giải thuật được mô tả như sau: 
Bước 1. Xét tất cả các NCCN mà NCSX1 có thể nhận 
được, thử cho NCSX1 nhận lần lượt các NCCN đó. 
Với mỗi NCCN thử cho NCSX1 tiến hành kiểm tra: 
- Nếu NCSX1 thỏa mãn điều kiện nhịp thì 
chuyển NCSX1 vào Tập NCSX. 
- Nếu NCSX1 không thỏa mãn điều kiện nhịp, 
xét tiếp các NCCN còn lại thỏa mãn điều kiện trình tự 
và thiết bị để ghép với NCCN đã có trong NCSX1, thử 
cho NCSX1 nhận lần lượt các NCCN đó. Với mỗi 
bước thử lại tiến hành kiểm tra điều kiện nhịp, nếu 
không tìm được thì chuyển NCSX1 vào Tập NCSX. 
Với mỗi kết quả tìm được NCSX1 ta sẽ thực hiện: 
Bước 2. Xét tất cả các NCCN mà NCSX2 có thể nhận 
được, thử cho NCSX2 nhận lần lượt các giá trị đó. Với 
mỗi NCCN thử cho NCSX2 tiến hành kiểm tra như 
bước 1. 
Tiếp tục như vậy đến bước k: 
Bước k. Giả sử tất cả các NCCN từ 1 cho đến k-1 đã 
được xếp vào Tập NCSX, tiếp tục xét đến NCCN thứ 
k (Try(k)). Có hai trường hợp xảy ra:. 
Trường hợp 1: NCCN thứ k đã được xếp vào 
cùng nhóm với các NCCN trước đó. 
Trường hợp 2: NCCN thứ k chưa được xếp vào 
nhóm nào. 
Tiến hành xử lí từng trường hợp như sau: 
- Trường hợp 1: NCCN thứ k đã được xếp. 
Nếu k = n, nghĩa là mọi NCCN đã được xếp 
thì chuyển Tập NCSX này đến một hàm Xuat(), hàm 
này xét xem Tập NCSX có số công nhân nhỏ hơn Tập 
NCSX trước đó không, nếu có số công nhân nhỏ hơn 
thì sẽ xuất còn không thì bỏ qua. 
Nếu k < n, vì NCCNk đã được xếp, công việc 
tiếp theo sẽ xét đến NCCN thứ k + 1. 
- Trường hợp 2: NCCN thứ k chưa được xếp. 
Nếu k = n, nghĩa là mọi NCCN trước đó đã 
được xếp, cho NCCN này trở thành một NCSX rồi 
chuyển vào Tập NCSX. 
Nếu k < n, sẽ lập ra một NCSX mới chứa 
NCCNk, khi đó phải tìm các NCCN khác có thể ghép 
được với NCCNk. Quá trình tìm kiếm kết thúc khi 
thành Tập NCSX hoàn chỉnh. Bảng mã giả tối ưu cân 
bằng chuyền được minh họa trong bảng 2. 
Bảng 2. Bảng mã giả tối ưu cân bằng chuyền 
Khởi tạo Tập NCSX để chứa các NCSX. 
Try( k ){ 
If Nếu NCCN k chưa được thêm vào NCSX 
then 
 Tạo một NCSX mới chứa NCCN k; 
 Đánh dấu đã thêm k; 
 if k == n then 
 Thêm NCCN vào NCSX; 
 Xuất; 
 else 
 // Kết hợp các NCCN khác với 
NCCN thứ k để tạo thành một NCSX 
 // Xét các NCCN khác từ k+1 đến n 
 for i1, i2, .. ∈ k + 1 .. n then 
 if Nếu NCCN thứ i chưa 
được thêm vào NCSX, đồng thời thỏa mãn các 
điều kiện về thiết bị, trình tự và thời gian không 
vượt quá 3.3R then 
 Thêm các NCCN thỏa mãn vào 
NCSX; 
 Thêm NCSX vào Tập NCSX; 
 Try (k+1); 
 Bỏ NCSX ra khỏi Tập NCSX; 
 Đánh dấu k tự do; 
else // k đã được thêm vào một NCSX trước đó 
trong Tập NCSX. 
 if k == n then 
 Xuất; 
 else Try(k+1); 
} 
Tạp chí Khoa học và Công nghệ 141 (2020) 034-041 
39 
Bảng 3. Các kết quả xây dựng NCSX với R = 64 giây, Nsx = 25 người 
3.2. Kết quả tối ưu cân bằng dây chuyền may sản 
phẩm Polo-Shirt. 
3.2.1. Kết quả cân bằng dây chuyền may sản phẩm 
Polo-Shirt với P= 450 (Sp/ca) 
Áp dụng thuật toán tối ưu cân bằng chuyền được 
thiết kế bằng chiến lược vét cạn, tiến hành xây dựng 
các NCSX để may sản phẩm Polo-Shirt với P = 450 
(sp/ca), Tlvca = 28800 (giây), R = 64 (giây), Rmin = 58 
(giây); Rmax = 70 (giây). Trong tất cả các kết quả tìm 
được, chọn ra 7 kết quả có số công nhân nhỏ nhất là 
25 công nhân được trình bày trong bảng 3. Hiệu quả 
tổ chức của dây chuyền (LE) của tất cả 7 kết quả đều 
bằng 93%, trong đó kết quả Tập NCSX 7 có số NCSX 
có nhịp riêng nằm trong khoảng giới hạn nhịp là 16 
trên tổng số 19 NCSX chiếm 84,2%, đây là giá trị là 
lớn nhất so với 6 kết quả còn lại, biểu đồ phụ tải được 
minh họa trong hình 5, trong các kết quả tìm được thì 
Tập NCSX 7 cho kết quả cân bằng chuyền tốt nhất. 
Hình 5. Biểu đồ phụ tải của các NCSX Tập NCSX 7 
Bảng 4. Kết quả cân bằng chuyền với 8 mức nhịp 
R 
(giây) 
Nsx 
(người) 
LE 
(%) 
H1 
(%) 
58 28 91.6 80 
60 28 88.5 76.2 
62 25 95.9 90.5 
64 25 92.9 84.2 
66 25 90.1 78.9 
68 25 87.5 68.4 
70 24 88.5 68.4 
72 24 86.1 50 
3.2.2. Kết quả cân bằng dây chuyền may sản phẩm 
Polo-Shirt khi thay đổi nhịp dây chuyền 
Công suất thiết kế cho mỗi dây chuyền may sản 
phẩm Polo-Shirt là P = 400-500 (sp/ca), nếu P = 400 
(sp/ca) thì R = 58 (giây), nếu P = 500 (sp/ca) thì R = 
72 (giây). Cho nhịp tăng từ 58 đến 72 giây, mỗi lần 
nhịp tăng 2 đơn vị, tại mỗi giá trị của nhịp chọn các 
kết quả có số công nhân nhỏ nhất, trong các kết quả 
đó lại chọn ra kết quả có tỷ lệ số NCSX có nhịp riêng 
nằm trong khoảng giới hạn nhịp là nhiều nhất được 
trình bày trong bảng 4 gồm 8 kết quả. 
Trong 8 kết quả thu được, mức nhịp R = 62 giây 
cho giá trị hiệu quả dây chuyền LE = 95.9% là cao 
nhất so với 7 mức nhịp còn lại, mức nhịp R = 62 giây 
cũng cho kết quả tỷ lệ số NCSX có nhịp riêng nằm 
trong khoảng giới hạn nhịp H1 =90,5% là cao nhất so 
với 7 mức nhịp còn lại. Kết quả phối hợp các NCCN 
thành NCSX ở mức nhịp R = 62 giây được trình bày 
trong bảng 5, mỗi NCSX chỉ gồm 1 đến 2 NCCN, cần 
1 đến 2 công nhân, các NCSX này đảm bảo điều kiện 
ràng buộc về thiết bị. Số NCSX có nhịp riêng nằm 
Tạp chí Khoa học và Công nghệ 141 (2020) 034-041 
40 
trong khoảng giới hạn nhịp 56 ÷ 68 (giây) là 19 
NCSX trên tổng số 21 NCSX, biểu đồ phụ tải được 
minh họa trong hình 6. Như vậy ở mức nhịp R = 62 
giây, xây dựng được Tập NCSX có hiệu quả dây 
chuyền và tỷ lệ NCSX nằm trong khoảng dao động 
nhịp là cao nhất so với các mức nhịp còn lại. 
Hình 6. Biểu đồ phụ tải của các NCSX với R = 62 
(giây), Nsx = 25 (người). 
Bảng 5. Kết quả xây dựng NCSX với R = 62 giây 
NCSX Tập 
NCSX 
Thiết 
bị 
tsxj 
(giây) 
Ncj 
(người) 
Rj 
(giây) 
1 1-5 MC2K 64 1 64 
2 2 MB1K 56 1 56 
3 3 MB1K 128 2 56 
4 4-16 MB1K 62 1 62 
5 6-9 MX2K 56 1 56 
6 7 MC1K 32 1 32 
7 8 MB1K 56 1 56 
8 10 MB1K 56 1 56 
9 11-12 MB1K 60 1 60 
10 13 BL 60 1 60 
11 14-15 MB1K 119 2 60 
12 17-18 MB1K 65 1 65 
13 19 MX2K 63 1 63 
14 20 MB1K 63 1 63 
15 21 MX2K 68 1 68 
16 22 MC1K 68 1 68 
17 23 MX2K 120 2 60 
18 24-26 MB1K 117 2 59 
19 25 MC2K 68 1 68 
20 27-28 MDB 42 1 42 
21 29-30 
MTK 
MDC 64 1 64 
Tổng 25 
4. Kết luận chung 
Trong bài báo này, chiến lược vét cạn được áp 
dụng để tìm ra kết quả cân bằng chuyền khi cho trước 
nhịp của dây chuyền. Trên cơ sở phân tích các điều 
kiện thực tế sản xuất tại nhà máy may Đồng Văn, tiến 
hành xác định các điều kiện ràng buộc về trình tự 
thực hiện, thiết bị và số lượng công nhân trong mỗi 
NCSX. Bước đầu các NCCN được phối hợp lại với 
nhau sao cho nhịp riêng của các NCSX thỏa mãn 
khoảng giới hạn nhịp, các ràng buộc về trình tự thực 
hiện và điều kiện ghép thiết bị, số lượng công nhân 
trong mỗi NCSX phải thỏa mãn. Có nhiều cách để 
phối hợp các NCCN thành NCSX mà vẫn thỏa mãn 
các điều kiện ràng buộc, trong các kết quả đó chọn ra 
các kết quả có số công nhân ít nhất để hiệu quả dây 
chuyền cao nhất có thể. Để thời gian làm việc của 
mỗi công nhân đồng đều nhau, bước tiếp theo tiến 
hành chọn trong các kết quả đó có số NCSX nằm 
trong khoảng giới hạn nhịp là nhiều nhất. Trong cách 
tiếp cận chiến lược vét cạn sẽ cho kết quả tối ưu. 
Sự thay đổi về nhịp của dây chuyền sẽ dẫn đến 
các kết quả cân bằng khác nhau, nó đòi hỏi phải cân 
bằng lại chuyền và tái phân bổ các nguồn lực. Kết 
quả nghiên cứu cho thấy khi thay đổi nhịp của dây 
chuyền sẽ cho các kết quả rất khác biệt. 
Do sự tiện ích trong sử dụng nên hiện nay nhu 
cầu tiêu thụ về nhóm chủng loại quần áo từ vải dệt 
kim nói chung và sản phẩm áo Polo-Shirt nói riêng là 
rất lớn trên thị trường thế giới và Việt Nam. Trong 
thực tế sản xuất sản phẩm này, sự thay đổi mặt hàng 
diễn ra thường xuyên do sự phong phú, đa dạng về 
kiểu dáng, kết cấu công nghệ may, thiết bị sản xuất. 
Do vậy, việc thiết lập một phần mềm giải quyết các 
bài toán cân bằng chuyền trong thực tế sản xuất là cần 
thiết. Tuy nhiên, nghiên cứu mới dừng lại ở việc xây 
dựng phần mềm cân bằng chuyền trong điều kiện 
thực tế sản xuất của nhà máy may Đồng Văn, cần 
phát triển bài toán cân bằng chuyền cho các hình thức 
tổ chức sản xuất của các chủng loại sản phẩm khác từ 
đó làm cơ sở cho việc xây dựng các phần mềm cân 
bằng dây chuyền theo đặc thù sản xuất ngành may 
công nghiệp. 
Lời cảm ơn 
Nhóm tác giả chân thành cảm ơn sự hỗ trợ của 
nhà máy may Đồng Văn, Tổng công ty CP Dệt May 
Hà Nội đã tạo điều kiện cho chúng tôi khảo sát, thực 
nghiệm để hoàn thành nghiên cứu này. 
Tài liệu tham khảo 
[1] N. Kriengkorakot and N. Pianthong, The assembly line 
balancing problem: Review Problem, Journal of 
Industrial Engineering, vol. 34 (2007) pp. 133–140. 
[2] S. Ghosh and R. J. Gagnon, A comprehensive 
literature review and analysis of the design, balancing 
and scheduling of assembly systems, International 
Journal of Production Research, vol. 27, no. 4 (1989) 
pp. 637–670. 
[3] A. Scholl and C. Becker, State-of-the-art exact and 
heuristic solution procedures for simple assembly line 
balancing, European Journal of Operational Research, 
vol. 168, no. 3 (2006) pp. 666–693. 
[4] D. S. M. S. Santosh T. Ghutukade, Use of Ranked 
Position Weighted Method For Assembly Line 
Tạp chí Khoa học và Công nghệ 141 (2020) 034-041 
41 
Banlancing, International Journal of Advanced 
Engineering Research and Studies (2013) pp. 5–7. 
[5] V. V Pachghare and R. S. Dalu, Assembly Line 
Balancing Methods–A Case Study, International 
Journal of Science and Research vol. 3, no. 5 (2012) 
pp. 2319–7064. 
[6] S. ERYÜRÜK, Clothing Assembly Line Design Using 
Simulation and Heuristic Line Balancing Techniques, 
Journal of Textile & Apparel/ Tekstil ve Konfeksiyon, 
no. 4 (2012), 360–368 
[7] A. Jayakumar and A. K. Krishnaraj, Productivity 
Improvement in Stitching Section of a Garment 
Manufacturing Company, International Journal of 
Innovative Research in Advanced Engineering, vol. 4, 
no. 12 (2017) pp. 8–11. 
[8] J. C. Chen, C.-C. Chen, L.-H. Su, H.-B. Wu, and C.-J. 
Sun, Assembly line balancing in garment industry, 
International Conference on Industrial Engineering 
and Operations Management Bali, Indonesia, January 
7 – 9 (2014) pp. 1215–1225. 
[9] Nguyễn Đức Nghĩa, Cấu trúc dữ liệu và thuật toán, 
NXB Đại học Bách khoa Hà Nội, 2013. 
[10] Tổng công ty Dệt May Hà Nội, Tài liệu kỹ thuật công 
nghệ sản phẩm áo Polo-Shirt, 2018.