Tài liệu Giải thuật tabu cho bài toán cân bằng dây chuyền sản xuất dạng 2

Mẩu T.08 ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA FOG BÁO CÁO TỔNG KẾT KẾT QUẢ ĐỀ TÀI KHCN CẤP TRƯỜNG Tên đề tài: GIẢI THUẬT TABU CHO BÀI TOÁN CÂN BẰNG DÂY CHUYỀN SẢN XUẤT DẠNG 2 (Tabu search approach for type 2 problem of assembly line balancing) Mã số đề tài: T-QLCN-2012-69 Thời gian thực hiện: từ tháng 02/2012 đến 02/2013 (01 năm) Chủ nhiệm đề tài: GVC. ThS. Đường Võ Hùng Cán bộ tham gia đề tài: GVC. ThS. Đường Võ Hùng Thành phố Hồ Chí Minh – Tháng 02 / 2013 Lời cảm ơn Sau 01 năm thực hiện đề tài “Giải thuật Tabu cho bài toán cân bằng dây chuyền sản xuất dạng 2”, tác giả cũng đã hoàn thành cơ bản yêu cầu đặt ra, đề tài cũng thu được một số kết quả nhất định. Tuy nhiên, đề tài này sẽ không thể thành công nếu không có sự giúp đỡ từ vật chất đến tinh thần, hỗ trợ, chia sẻ khó khăn từ quý phòng ban, đến đồng nghiệp, bạn bè. Nhân dịp này, tác giả cũng có cơ hội nói lên lời cảm ơn chân thành của mình: Xin chân thành cảm ơn Đại học Quốc gia Tp. Hồ Chí Minh, Trường Đại học Bách khoa Tp. Hồ Chí Minh đã tài trợ nguồn kinh phí đáng kể để tác giả hoàn thành đề tài. Xin chân thành cảm ơn Phòng Khoa học Công nghệ và Dự án đã tạo điều kiện thuận lợi, cũng như giúp đỡ tác giả rất nhiều trong suốt quá trình thực hiện đề tài. Xin chân thành cảm ơn Khoa Quản lý Công nghiệp, Bộ môn Quản lý sản xuất và điều hành đã tạo điều kiện thuận lợi, giúp đỡ, hỗ trợ chuyên môn để tác giả hoàn thành đề tài đúng tiến độ. Xin gửi lời cảm ơn đến đồng nghiệp và bạn bè đã chia sẻ những khó khăn, trao đổi thông tin, kinh nghiệm để tác giả hoàn thành đề tài này. Xin chân thành cảm ơn. Tác giả Đường Võ Hùng i Tóm tắt Đề tài “Giải thuật Tabu cho bài toán cân bằng dây chuyền sản xuất dạng 2 – Tabu search approach for type 2 problem of assembly line balancing” đã hoàn thành, và cũng có một số kết quả nhất định. Trong đề tài này, tác giả đã ứng dụng thành công thuật toán Tabu (Tabu search) cho bài toán cân bằng dây chuyền sản xuất dạng 2 và cho cả bài toán cân bằng dây chuyền sản xuất tổng quát. Tabu là giải thuật gần đúng để giải bài toán lớn đã được ứng dụng trong nhiều lĩnh vực. Đối với bài toán cân bằng dây chuyền sản xuất dạng 2, nghiên cứu này đã xây dựng 2 giải thuật để giải quyết, kết quả của từng giải thuật được so sánh, kiểm chứng với những công trình đã được công bố, cũng như kết quả từ chương trình LINGO. Kết quả của giải thuật đáng tin cậy và có thể ứng dụng cho bài toán tái thiết kế dây chuyền (tận dụng lại dây chuyền cũ khi đầu tư chưa lâu), giải thuật này rất phù hợp với điều kiện của Việt nam. Các nhà sản xuất có thể chuyển đổi cơ cấu sản xuất sản phẩm khi nhu cầu về sản phẩm đang sản xuất bị suy giảm. Điều thành công của giải thuật là hiệu quả của quá trình tái thiết kế, giải thuật sẽ chỉ ra những trạm làm việc không cần thiết cho dây chuyền mới, và loại ra khỏi dây chuyền này. Như vậy giải thuật sẽ giúp giảm chi phí đầu tư và chi phí vận hành. Bên cạnh đó, nghiên cứu cũng so sánh điều kiện cải thiện cũng như thay đổi lời giải ban đầu cung cấp cho giải thuật để xem xét ảnh hưởng của những thay đổi này đến giải thuật, nhằm hoàn thiện giải thuật Tabu đối với bài toán cân bằng dây chuyền sản xuất. Nghiên cứu cũng có một số kết quả đáng tin cậy, lời giải nhanh chóng giúp cho các nhà đầu tư có thể ra quyết định trong việc tự đầu tư chế tạo ra dây chuyền sản xuất mới. Như vậy giải thuật hoàn toàn phù hợp với những công ty muốn mở rộng sản xuất nhưng không phải nhập dây chuyền sản xuất từ nước ngoài. Tiết kiệm chi phí đầu tư cho doanh nghiệp. Từ khóa: cân bằng dây chuyền sản xuất – assembly line balancing, thuật toán Tabu – Tabu search. ii MỤC LỤC Chương 01 02 03 04 05 Nội dung Trang Lời cảm ơn i Tóm tắt đề tài ii Mục lục iii TỔNG QUAN 01 1.1 Giới thiệu 01 1.2 Mục tiêu của nghiên cứu 02 1.3 Giới hạn của nghiên cứu 02 CƠ SỚ LÝ THUYẾT 03 2.1 Giới thiệu 03 2.2. Bài toán cân bằng dây chuyền sản xuất 04 2.3 Thuật toán Tabu cho bài toán cân bằng dây chuyền sản xuất 05 GIẢI THUẬT TABU 08 3.1 Giải thuật Tabu cho bài toán cân bằng dây chuyền sản xuất dạng 2 08 3.2 Thuật toán Tabu cho bài toán cân bằng dây chuyền sản xuất dạng 2 10 3.3 Thay đổi lời giải ban đầu kết hợp điều kiện cải thiện lời giải 10 3.4 Một số sơ đồ khối của giải thuật 11 KẾT QUẢ NGHIÊN CỨU 16 4.1 Kết quả nghiên cứu với bài toán dạng 2 16 4.2 Kết quả nghiên cứu với bài toán tổng quát 19 KẾT LUẬN VÀ KIẾN NGHỊ 23 5.1 Kết luận 23 5.2 Kiến nghị 23 TÀI LIỆU THAM KHẢO 24 iii CHƯƠNG 1 TỔNG QUAN 1.1. Giới thiệu Chúng ta biết rằng, nền công nghiệp sản xuất Việt nam chúng ta cũng thăng trầm theo xu hướng chung của nền kinh tế nước ta và thế giới. Trong khoảng 02 thập niên trở lại đây, Việt nam đã và đang được nhiều quốc gia đầu tư vào nền sản xuất công nghiệp, nhiều dây chuyền sản xuất được nhập vào Việt nam để hỗ trợ nền sản xuất của chúng ta phát triển. Khi sản xuất thuận lợi thì việc một công ty hay nhà đầu tư bỏ ra một khoảng tiền lớn để đầu tư vào sản xuất thì không gặp vấn đề trở ngại, khó khăn. Tuy nhiên, khi nền kinh tế trở nên khó khăn trong những năm gần đây thì việc tìm kiếm nguồn kinh phí đầu tư cho dây chuyền sản xuất thật sự khó khăn. Do vậy, nếu các công ty sản xuất của Việt nam có thể tự thiết kế các dây chuyền sản xuất theo yêu cầu nhưng với chi phí thấp hơn những dây chuyền phải nhập từ nước ngoài là một vấn đề cần được quan tâm. Để đáp ứng được nhu cầu trên, hỗ trợ cho thiết kế dây chuyền là một trong những vấn đề cần được nghiên cứu, trong đó, bài toán cân bằng dây chuyền sản xuất (assembly line balancing problems) là một trong những vấn đề cần phải có lời giải khi bài toán thiết kế được đặt ra. Đây cũng là một trong những yêu cầu thực hiện của nghiên cứu này. Ngoài ra, bài toán cân bằng dây chuyền sản xuất cũng là một trong những vấn đề thuộc chuyên môn sâu của bộ môn quản lý sản xuất và điều hành, thuộc Khoa Quản lý Công nghiệp, Đại học Bách khoa Tp. Hồ Chí Minh. Thực hiện nghiên cứu này cũng là một nhiệm vụ quan trọng trong công tác chuyên môn của bộ môn. Chúng ta biết rằng bài toán cân bằng dây chuyền sản xuất được phân thành 2 dạng (Mastor, 1970, Hùng, 2011). Dạng 1: với thời gian chu kỳ cho trước, thiết kế dây chuyền sản xuất với số trạm làm việc là ít nhất, bài toán này tương ứng với việc thiết kế mới dây chuyền; Dạng 2: dựa trên dây chuyền sản xuất đã có sẵn (biết trước số trạm làm việc) tái thiết kế dây chuyền sản xuất với sản lượng là cao nhất, hay nói cách khác thời gian chu kỳ là nhỏ nhất, bài toán này tương ứng với việc tận dụng lại dây chuyền cũ sao cho hiệu quả nhất. Trong điều kiện sản xuất của Việt nam hiện nay, thiết kế mới hay tận dụng lại dây chuyền đã đầu tư chưa lâu vẫn thực sự cần thiết cho các nhà quản lý và đầu tư. Chúng ta biết rằng, các doanh nghiệp sản xuất của Việt nam thường phải nhập dây chuyền sản xuất từ nước ngoài, giá thành công nghệ là khá cao trong việc đáp ứng nhu cầu sản xuất. Hơn nữa, khi đã đầu tư công nghệ sản xuất, thì công nghệ bị lỗi thời cũng là một vấn đề lớn, tận dụng lại cũng là một thách thức đối với các nhà thiết kế, quản lý và đầu tư (Hùng, 2011), đều này cần thêm nữa những nghiên cứu cho bài toán cân bằng dây chuyền sản xuất. Tuy nhiên, bản chất của bài toán cân bằng dây chuyền sản xuất là khá phức tạp, tổ hợp lời giải lớn, đòi hỏi mô hình và thuật toán phù hợp (Suresh, et al., 1994, Bautista and Pereira, 2007, 2009, Hùng, 2004, 2011,…) Đối với bài toán cân bằng, là một dạng bài toán tổ hợp nên tập lời giải khá lớn đòi hỏi kỹ thuật giải phức tạp, nên trong khoảng 2 thập niên trở lại đây người ta bắt đầu đưa ra nhiều giải thuật với mục tiêu đáp ứng được cho bài toán lớn trong cân bằng dây chuyền sản xuất (xem thêm trong phần cơ sở lý thuyết – chương 2). Một trong những giải thuật hiện nay thường được áp dụng cho việc tìm lời giải gần tối ưu đó là giải thuật Tabu. Trong nghiên cứu này, một lần nữa giải thuật Tabu được áp dụng để giải quyết bài toán cân bằng dây chuyền sản xuất. 1 Nghiên cứu này được thực hiện nhằm trả lời một số câu hỏi như sau: Làm thế nào để xây dựng dây chuyền sản xuất một cách nhanh chóng và hiệu quả, giúp các nhà quản lý và đầu tư ra quyết định hợp lý về việc đầu tư dây chuyền mới theo nhu cầu sản xuất đặt trước (bài toán cân bằng dây chuyền sản xuất dạng 1)? Làm thế nào để tái thiết kế và sử dụng dây chuyền cũ (đã đầu tư chưa lâu) một cách hiệu quả (bài toán cân bằng dây chuyền sản xuất dạng 2)? Để có thể trả lời cho các câu hỏi này, nhiều nghiên cứu đã được thực hiện như như Mastor (1970), Bowman (1960), và gần đây có các nghiên cứu như Suresh, et al., 1994, Bautista and Pereira, 2007, 2009, Hùng, 2004, 2011,… Tuy nhiên, bài toán cân bằng dây chuyền sản xuất là dạng bài toán phức tạp, tập lời giải lớn làm cho nhiệm vụ xác định lời giải khá phức tạp, đòi hỏi kỹ thuật giải cao cấp, cần nhiều thời gian và chi phí. Mặc dù, hiện nay có nhiều giải thuật để giải quyết bài toán lớn, nhưng Tabu vẫn được xem làm một trong những giải thuật hiệu quả và cần thiết trong việc xác định lời giải. Do vậy, trong nghiên cứu này, một lần nữa Tabu được ứng dụng để giải quyết bài toán này, ngoài ra, nghiên cứu này cũng muốn hoàn thiện giải thuật Tabu cho bài toán cân bằng dây chuyền sản xuất. Trong khi đó theo điều kiện nghiên cứu của Việt nam hiện nay, các nghiên cứu về bài toán cân bằng dây chuyền sản xuất, cũng như các ứng dụng thuật toán Tabu rất hiếm. Đây cũng là một cơ hội để tác giả thực hiện nghiên cứu này. Ngoài việc thực hiện giải thuật cho bài toán cân bằng dây chuyền sản xuất dạng 2, nghiên cứu này muốn hoàn thiện giải thuật Tabu bằng cách mở rộng nghiên cứu của Hùng (2004, 2011) áp dụng cho bài toán dạng 1 và dạng 2 trong việc so sánh sự thay đổi lời giải ban đầu cung cấp cho giải thuật, và chiến lược khảo sát tập lời giải (tương tự như Chiang, 1998), đồng thời nghiên cứu cũng khảo sát điều kiện thoát khi vùng lân cận mới không cải thiện được lời giải để tránh việc giải thuật cho lời giải tối ưu cục bộ. 1.2. Mục tiêu của nghiên cứu Thực hiện nghiên cứu này nhằm đáp ứng một số mục tiêu sau: - Xây dựng giải thuật Tabu cho bài toán cân bằng dây chuyền sản xuất dạng 2. - Hoàn thiện thuật toán Tabu cho bài toán cân bằng dây chuyền sản xuất (dạng 1 và 2) - Ứng dụng giải thuật cho một bài toán thực tế. 1.3. Giới hạn của nghiên cứu Đây là bài toán hỗ trợ cho thiết kế dây chuyền sản xuất (bài toán thiết kế mới – dạng 1) và bài toán tái thiết kế dây chuyền một cách hiệu quả (bài toán tận dụng dây chuyền đã qua sử dụng – dạng 2), các thông số sản xuất như sản lượng sản xuất phải được đặt ra, quy trình công nghệ của sản phẩm biết trước, các thông số về thời gian gia công các công đoạn là xác định và biết trước. 2 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT 2.1. Giới thiệu Chúng ta biết rằng bài toán cân bằng dây chuyền sản xuất được phân thành 2 dạng (Mastor, 1970, Hùng, 2011) như sau: Dạng 1: với thời gian chu kỳ cho trước, thiết kế dây chuyền sản xuất với số trạm làm việc là ít nhất, bài toán này tương ứng với việc thiết kế mới dây chuyền; Dạng 2: dựa trên dây chuyền sản xuất đã có sẵn (biết trước số trạm làm việc) tái thiết kế dây chuyền sản xuất với sản lượng là cao nhất, hay nói cách khác thời gian chu kỳ là nhỏ nhất, bài toán này tương ứng với việc tận dụng lại dây chuyền cũ sao cho hiệu quả nhất. Trong điều kiện sản xuất của Việt nam hiện nay, thiết kế mới hay tận dụng lại dây chuyền đã đầu tư chưa lâu vẫn thực sự cần thiết cho các nhà quản lý và đầu tư. Chúng ta biết rằng, các doanh nghiệp sản xuất của Việt nam thường phải nhập dây chuyền sản xuất từ nước ngoài, giá thành công nghệ là khá cao trong việc đáp ứng nhu cầu sản xuất. Hơn nữa, khi đã đầu tư công nghệ sản xuất, thì công nghệ bị lỗi thời cũng là một vấn đề lớn, tận dụng lại cũng là một thách thức đối với các nhà thiết kế, quản lý và đầu tư (Hùng, 2011), điều này cần thêm nữa những nghiên cứu cho bài toán cân bằng dây chuyền sản xuất. Tuy nhiên, bản chất của bài toán cân bằng dây chuyền sản xuất là khá phức tạp, tổ hợp lời giải lớn, đòi hỏi mô hình và thuật toán phù hợp (Suresh, et al., 1994, Bautista and Pereira, 2007, 2009, Hùng, 2004 & 2011,…) Để tìm lời giải cho bài toán cân bằng dây chuyền sản xuất, các nhà nghiên cứu đã bắt đầu thực hiện từ những năm 50 của thế kỷ trước như Mastor (1970), Bowman (1960),… Tuy nhiên, để có thể giải được bài toán cân bằng dây chuyền sản xuất, chúng ta cần nhiều giải thuật có thể giải được bài toán lớn và cho lời giải nhanh chóng, đủ độ tin cậy cần thiết. Ngày nay, có nhiều phương pháp giải đã được công bố trên các tạp chí quốc tế như Patterson và Albracht (1975) đã thành công khi áp dụng bài toán quy hoạch 0 –1 trong nghiên cứu của mình; Bowman (1960) đã đề nghị hai mô hình quy hoạch nguyên dùng cho bộ dữ liệu xác định. Bên cánh đó, quy hoạch động cũng là một trong những phương pháp được công bố và áp dụng thành công như công trình của Held, et al., (1963), và Bautista and Pereira (2009). Tuy nhiên, mô hình quy hoạch động của Held, et al., (1963) thì chỉ áp dụng cho bài toán nhỏ; trong khi đó, Bautista and Pereira (2009) áp dụng được cho bài toán lớn dựa trên nền tảng lời giải gần đúng để phân bổ công việc. Ngoài ra, những giải thuật hiện đại khác cũng lần lượt được công bố và áp dụng như kỹ thuật SA (Simulated Annealing) được nghiên cứu bởi Suresh và Sahu (1994), và Woodruff (1994); giải thuật gen (genetic) cho lời giải gần đúng cũng được công bố bởi Suresh, et al., (1996); trong khi đó, Yasunori, et al., (1994) đã đề nghị một giải pháp mới để giải quyết bài toán lớn bằng cách áp dụng giải thuật mạng Hopfield. Thời gian gần đây, để giải quyết ràng buộc về thời gian và sức chứa kho bãi, ràng buộc cơ bản về năng lực hỗ trợ cho sản xuất, Bautista và Pereira (2007) áp dụng thành công giải thuật Ant (Ant algorithm) trong nghiên cứu của mình. Mặc dù nhiều thuật toán đã được công bố và ứng dụng để cung cấp lời giải cho bài toán cân bằng dây chuyền sản xuất, tuy nhiên những giải thuật này khá phức tạp để hiểu, đòi hỏi những kỹ thuật tính toán cao cấp. Do vậy, trong khoảng 2 thập niên trở lại đây, từ khi thuật 3 toán TABU được công bố (Glover, 1990) và ứng dụng rộng rãi cho nhiều lĩnh vực, đặc biệt đối với bài toán mà tập lời giải lớn và phức tạp, mở ra những hướng nghiên cứu mới. Giải thuật này rất phù hợp với bài toán cân bằng dây chuyền sản xuất, nên ngày càng nhiều công trình nghiên cứu ứng dụng liên quan đến giải thuật được công bố trên các tạp chí khoa học như Chiang (1998), Hùng (2004&2011), Lapierre et al., (2006) và Ozcan và Toklu (2009),… Trong khi đó theo điều kiện nghiên cứu của Việt nam hiện nay, các nghiên cứu về bài toán cân bằng dây chuyền sản xuất, cũng như các ứng dụng thuật toán Tabu rất hiếm. Đây cũng là một cơ hội để tác giả thực hiện nghiên cứu này. Trong nghiên cứu này, một lần nữa giải thuật Tabu được ứng dụng để giải quyết bài toán cân bằng dây chuyền sản xuất. Nghiên cứu này mở rộng nghiên cứu của Hùng (2004, 2011) áp dụng cho bài toán dạng 1 và dạng 2 bằng cách so sánh sự thay đổi lời giải ban đầu cung cấp cho giải thuật, và chiến lược khảo sát tập lời giải (tương tự như Chiang, 1998), đồng thời nghiên cứu cũng khảo sát điều kiện thoát khi vùng lân cận mới không cải thiện được lời giải để tránh việc giải thuật cho lời giải tối ưu cục bộ. Kết quả của nghiên cứu được kiểm tra với những kết quả được công bố trên các tạp chí, nhằm kiểm chứng độ tin cậy của giải thuật. 2.2. Bài toán cân bằng dây chuyền sản xuất: Theo Mastor (1970), Hùng (2011), bài toán cân bằng dây chuyền sản xuất được chia thành 2 dạng, và được nghiên cứu rất nhiều trong khoảng 1 – 2 thập niên trước, chủ yếu tập trung vào bài toán dạng 1. Bài toán dạng 1 được hiểu là bài toán thiết kế mới dây chuyền sản xuất với yêu cầu về sản lượng cho trước. Hàm mục tiêu của bài toán 1 (theo Mastor 1970, Bowman 1960, Chiang 1998, Hùng 2004,…) là tối thiểu hóa số trạm làm việc hay Min. Z = n, với n là số trạm làm việc. Tuy nhiên, phần lớn những nghiên cứu về bài toán 1 đều dùng hàm mục tiêu tương đương khác để tiết giảm số trạm làm việc như sau: ⎛ ki ⎞ Max . Z = ∑ ⎜ ∑ t ij ⎟ ⎠ i =1 ⎝ j =1 n 2 với ki: số công việc được phân bổ vào trạm thứ i. (1) Trong khi đó, bài toán dạng 2 được hiểu là bài toán tận dụng dây chuyền sản xuất đã có để sản xuất sản phẩm khác. Trong điều kiện công nghệ thay đổi nhanh như hiện nay, bài toán dạng 2 ít được nghiên cứu hơn, tuy nhiên, với điều kiện sản xuất của Việt nam, thì bài toán dạng 2 vẫn có những ứng dụng nhất định (Hùng 2011). Hàm mục tiêu của bài toán này là tối thiểu hóa thời gian chu kỳ C (hay tối đa hóa sản lượng sản xuất trong cùng đơn vị thời gian), hàm mục tiêu có thể biểu diễn như sau: Min. Z=C Tương tự như bài toán dạng 1, hàm mục tiêu của bài toán dạng 2 cũng được viết lại dưới dạng khác với yêu cầu đảm bảo giảm thiểu thời gian chu kỳ như sau: ki n ki ⎛ ⎞ Min. Z = ∑⎜ C − ∑ tij ⎟ = n.C − ∑ ∑ tij i =1 ⎝ j =1 ⎠ i =1 j =1 n 4 (2) Trong đó: C: thời gian chu kỳ, ki: số công việc được phân bổ vào trạm thứ i, n: số trạm làm việc, tij: thời gian gia công của công việc j phân bổ vào trạm thứ i, Tương tự như những nghiên cứu trước, trong nghiên cứu này, hàm mục tiêu sử dụng để giải quyết bài toán chủ yếu là các hàm mục tiêu tương đương (1) và (2). Nghiên cứu này được thực hiên dựa trên giả thiết tất cả các thông số là xác định, hay nói cách khác thời gian công việc thành phần (tij) biết trước và không đổi. Như vậy, chúng ta thấy rằng sử dụng hai hàm mục tiêu (1) và (2) là tương đương với nhau và đạt được mục tiêu mong muốn tương ứng với bài toán 1 & 2. Để hỗ trợ cho giải thuật Tabu áp dụng cho bài toán cân bằng dây chuyền sản xuất dạng 2, nghiên cứu sẽ xây dựng và chứng minh một bổ đề như sau: Bổ đề: đối với bài toán cân bằng dây chuyền sản xuất dạng 2, thời gian chu kỳ C có được từ lời giải tối ưu sẽ giảm khi số trạm làm việc gia tăng. Chứng minh: giả sử chúng ta xem xét 2 trường hợp như sau: 1. thời gian chu kỳ tối ưu Cn với n trạm làm việc, 2. thời gian chu kỳ tối ưu Cn+k với (n+k) trạm làm việc, Nếu chúng ta xem xét trường hợp 2 với thời gian chu kỳ Cn ứng với n trạm làm việc, trong trường hợp này, chúng ta sẽ có thêm k trạm làm việc trống. Chúng ta biết rằng Cn là thời gian ứng với trạm làm việc được phân bổ dài nhất. Do đó, chúng ta có thể di chuyển bớt một số công việc được phân bổ vào trạm này đi đến 1 trong k trạm trống, như vậy sẽ đảm bảo thời gian chu kỳ tối ưu khi đó sẽ giảm. Điều này dẫn đến thời gian chu kỳ tối ưu trong trường hợp 2 sẽ nhỏ hơn hoặc bằng thời gian chu kỳ tối ưu trong trường hợp 1, hay nói một cách khác là Cn+k ≤ Cn, và bổ đề đã được chứng minh. Bổ đề này sẽ được sử dụng để thực hiện giải thuật giải quyết bài toán cân bằng dây chuyền sản xuất dạng 2 sẽ được trình bày trong chương 3 của báo cáo này. 2.3. Thuật toán TABU cho bài bài toán cân bằng dây chuyền sản xuất Thuật toán Tabu đã được nghiên cứu từ thập niên 80, 90 của thế kỷ trước và được Glover (1990) xây dựng thành khung hướng dẫn và đến nay được ứng dụng cho nhiều lĩnh vực khác nhau. Tuy được ứng dụng cho nhiều lĩnh vực khác nhưng ứng dụng trong việc giải quyết bài toán cân bằng dây chuyền sản xuất, đặc biệt là bài toán dạng 1, thì rất thành công như Chiang (1998), Hùng (2004), Lapierre et al., (2006) và Ozcan và Toklu (2009)... Đối với bài toán dạng 2 thì Hùng (2011) cũng đã nghiên cứu thành công mở ra hướng tận dụng lại những dây chuyền cũ cho điều kiện sản xuất của Việt nam. Thuật toán Tabu đã được đề cập trong nhiều nghiên cứu đã được công bố, tuy nhiên, nghiên cứu này cũng tóm lược nội dung chính của thuật toán Tabu và mở rộng nội dung tìm hiểu của nghiên cứu này. 5 2.3.1. Lời giải ban đầu – initial solution: chúng ta biết rằng Tabu là giải thuật tìm lời giải mới tiếp theo từ lời giải cũ đã có trước. Do vậy, ban đầu giải thuật Tabu cần lời giải đầu tiên làm lời giải xuất phát (lời giải này gọi là lời giải ban đầu), từ đó giải thuật sẽ tìm (search) vùng lân cận tìm lời giải tốt hơn để cải thiện lời giải hiện có (current solution). Tuy nhiên, giải thuật Tabu không tự xây dựng lời giải đầu tiên cho mình, do vậy, chúng ta phải cung cấp lời ban đầu này khi áp dụng Tabu. Theo những nghiên cứu trước đây (như Chiang 1998, Hùng 2004&2011...) thường sử dụng nguyên tắc công việc theo sau nhiều nhất, nếu có nhiều công việc thỏa mãn nguyên tắc này thì chọn công việc có thời gian gia công dài nhất. Chúng ta biết rằng, trong bài toán cân bằng dây chuyền sản xuất, khi xây dựng dây chuyền thì biểu đồ quan hệ tiên quyết (hay trật tự gia công trong quy trình công nghệ sản xuất, lắp ráp) phải được tuân thủ. Như vậy các công đoạn có vị trí phía sau trong quy trình công nghệ sẽ không được ưu tiên khi phân bổ vào các trạm làm việc, vì nó đòi hỏi những công đoạn trước phải được phân bổ hết. Như vậy, khi áp dụng nghiên tắc này, các công đoạn phía sau sẽ lần lược được “giải phóng release”, và dễ dàng được phân bổ. Đối với nhiều bài toán nhỏ, thì người ta xem lời giải từ nguyên tắc này như là lời giải gần đúng có thể chấp nhận được. Do yêu cầu phải có lời giải ban đầu, nên nghiên cứu muốn xem xét mức độ ảnh hưởng của lời giải này với kết quả của giải thuật. Trong nghiên cứu này nghiên tắc công việc theo sau dài nhất được gọi là phương pháp 1. Ngoài ra để so sánh và đánh giá, nghiên cứu dùng cách xây dựng lời giải ban đầu đơn giản hơn bằng cách phân bổ mỗi công việc vào một trạm làm việc, cách này được gọi là phương pháp 2. Cách này đơn giản hóa việc cấp lời giải đầu cho giải thuật, đơn giản hóa tính toán của giải thuật, tạo ra lời giải khả thi trực tiếp. Kết quả của nghiên cứu được trình bày và so sánh trong phần 4.2 của chương 4 trong báo cáo này. 2.3.2. Bộ nhớ - memory: đối với thuật toán Tabu, bộ nhớ dùng để kiểm soát tối ưu cục bộ của lời giải, trong hầu hết các nghiên cứu dùng mảng 2 chiều Tabu để kiểm soát di chuyển qua lại của các công đoạn giữa các trạm. Công đoạn thứ i được phân bổ vào trạm làm việc w sẽ được quản lý bằng Tabu[i][w], và sẽ được cập nhật khi công đoạn này chuyển qua trạm làm việc khác, và nếu việc di chuyển này giúp cải thiện giá trị hàm mục tiêu, thì di chuyển sẽ được chấp nhận. 2.3.3. Tiêu chuẩn chấp nhận thay đổi – aspiration criterion: đây là một tiêu chuẩn quan trọng để chấp nhận một lời giải mới tốt hơn lời giải tốt nhất đang lưu trong bộ nhớ, tiêu chuẩn này giúp lời giải được cải thiện liên tục cho đến khi đạt điều kiện dừng của giải thuật. 2.3.4. Đa dạng hóa tập lời giải – intensification and diversification: đa dạng hóa là một phần quan trọng của giải thuật trong việc tránh tối ưu cục bộ, bằng cách chấp nhận lời giải tốt nhất của tập lời giải hiện tại (mặc dù lời giải này có thể không tốt hơn lời giải hiện tại trong bộ nhớ - current solution). Trong trường hợp này giải thuật sẽ bị lặp vì không có lời giải nào cải thiện lời giải trong bộ nhớ, chúng ta dùng bộ nhớ tạm thời này để chấp nhận di chuyển nhằm tạo tập lời giải mới. 2.3.5. Tiêu chuẩn cải thiện lời giải – improvement strategy: tương tự như những công trình nghiên cứu trước, nghiên cứu này cũng dùng 2 hình thức cải thiện đó là: i) chấp nhận di chuyển đến tập lời giải mới khi tìm được lời giải cải thiện đầu tiên (first improvement – nguyên tắc 1), nguyên tắc này không tìm hết tập lời giải hiện tại; ii) chấp 6 nhận di chuyển khi toàn bộ tập lời giải hiện tại được khảo sát hết, và lời giải cải thiện nhất sẽ được chọn để thay thế lời giải tốt nhất (best improvement – nguyên tắc 2). Cả hai nguyên tắc đều được khảo sát và so sánh kết quả. Kết quả của cả hai nguyên tắc sẽ được trình bày và so sánh trong phần 4.2 của chương 4 trong báo cáo này. 2.3.6. Tiêu chuẩn chống tối ưu cục bộ – avoiding a local optima: trong trường hợp tập lời giải hiện tại không cho bất kỳ lời giải nào tốt hơn lời giải hiện tại (nonimprovement), theo tiêu chuẩn đa dạng hóa, giải thuật vẫn chấp nhận di chuyển và cập nhật lời giải hiện tại. Điều này dẫn đến lời giải hiện tại sẽ bị thay đổi (có thể giảm), do đó, nghiên cứu này có dùng thêm một bộ nhớ để lưu giữ lời giải tốt nhất cho đến hiện tại. Lời giải này chỉ được cập nhật khi giá trị lời giải được chấp nhận tốt hơn lời giải tốt nhất này. Tiêu chuẩn này của nghiên cứu đảm bảo khi đạt điều kiện thoát, lời giải tốt nhất sẽ được đảm bảo lưu giữ, đó là lời giải được xuất ra từ bộ nhớ này. Lời giải ban đầu Tìm kiếm lời giải, cập nhật bộ nhớ, và chấp nhận di chuyển Khảo sát vùng lân cận của lời giải hiện tại Lời giải tiếp theo Tiêu chuẩn chấp nhận thay đổi no Lời giải mới tốt hơn ? yes Điều kiện dừng ? yes Lời giải tốt nhất Sơ đồ 2.1: Giải thuật Tabu. 7 no CHƯƠNG 3 GIẢI THUẬT TABU CHO BÀI TOÁN CÂN BẰNG DÂY CHUYỀN SẢN XUẤT 3.1. Giải thuật cho bài toán cân bằng dây chuyền sản xuất dạng 2 Trong nghiên cứu này, hai giải thuật cho bài toán cân bằng dây chuyền sản xuất dạng 2 được thực hiện và so sánh kết quả. Kết quả của giải thuật được đăng trên tạp chí Phát triển khoa học & công nghệ, số Q2, tập 14, năm 2011 (có bài báo đính kèm). 3.1.1. Giải thuật 1 Từ bổ đề trong chương 2, chúng ta luôn luôn có Cn+k ≤ Cn, như vậy chúng ta hoàn toàn có thể giảm số trạm làm việc không cần thiết nếu xảy ra trường hợp Cn+k = Cn, khi đó chúng ta có k trạm trống. Bài toán sẽ trở nên dễ dàng hơn nếu mỗi lần chúng ta chỉ xét k = 1, như vậy mỗi bước lặp chúng ta sẽ giảm được 01 trạm trống. Giải thuật sẽ dừng lại khi bước lặp nào đó không thỏa điều kiện giảm thời gian chu kỳ. Giải thuật 1 được đề nghị như sau: Giải trực tiếp bài toán 2 với số trạm n = N (N số trạm làm việc cho trước), chúng ta xác định giá trị thời gian chu kỳ tối ưu Cn. Sau đó, chúng ta sẽ giải tiếp tục với n = (N – 1) xác định giá trị Cn-1 tương ứng. Nếu Cn = Cn-1, thì chúng ta tiếp tục với n = (N – 2) xác định giá trị Cn-2 tương ứng, và so sánh Cn-1 với Cn-2. Trong trường hợp tổng quát tại một bước giải nào đó có Cn ≠ Cn-1, chúng ta dừng giải thuật và thời gian chu kỳ tối ưu là Cn, tương ứng với số trạm làm việc là n (giải thuật được tóm tắt trong sơ đồ 3.1). Điểm thành công của giải thuật này là cho phép giảm mỗi lần 01 trạm làm việc trống ở mỗi bước lặp, như vậy chúng ta vẫn đảm bảo sản lượng theo yêu cầu thiết kế mà vẫn có thể tiết giảm số trạm làm việc không cần thiết, giảm chi phí trong vận hành. Đặc biệt, với bộ giá trị (Cn, n) chúng ta có thể lựa chọn tương ứng với từng mức sản lượng theo yêu cầu. 3.1.2. Giải thuật 2 Tương tự như giải thuật 1, thông qua bổ đề trong chương 2, chúng ta hoàn toàn có thể giải bài toán cân bằng dây chuyền sản xuất dạng 2 qua hai giai đoạn như sau (giải thuật được tóm tắt trong sơ đồ 3.2): a. Giai đoạn 1: giải trực tiếp bài toán dạng 2 với thông số yêu cầu (cực tiểu hóa thời gian lãng phí, n là số trạm làm việc cho trước, áp dụng thuật toán Tabu), kết thúc giai đoạn này, chúng ta sẽ có giá trị Cn tương ứng. b. Giai đoạn 2: giải lại theo thuật toán Tabu cho bài toán dạng 1 (với thời gian chu kỳ cho trước là Cn từ giai đoạn 1), kết quả của giai đoạn này cho chúng ta giá trị của số trạm làm việc n’. Nếu trong trường hợp n’ 0 yes yes i:= i + 1 Cn = Cn+1 no Lời giải tối ưu với C = Cn+1 Sơ đồ 3.1: Giải thuật 1 Bài toán dạng 2 (miniminze C) Thực hiện giải thuật với n: = N Thời gian chu kỳ tối ưu Cn Giai đoạn 1 Giai đoạn 2 Xây dựng lời giải ban đầu với thời gian chu kỳ bằng Cn Thực hiện giải thuật (cho bài toán 1, số trạm tối ưu n) Lời giải tối ưu với n, Cn Sơ đồ 3.2: Giải thuật 2 9 3.2. Thuật toán TABU chi tiết cho bài toán cân bằng dây chuyền sản xuất dạng 2 Thuật toán Tabu đã được nghiên cứu khá lâu và được nhiều tác giả trình bày khá chi tiết trong những công trình nghiên cứu trước, trong nghiên cứu này, tác giả cũng đã đề cập trong phần cơ sở lý thuyết (chương 2). Tuy nhiên, để chi tiết hóa giải thuật, đồng thời để người đọc có thể dễ dàng theo dõi, đối với nghiên cứu này, tác giả xin giới thiệu trực tiếp giải thuật Tabu mà tác giả đã ứng dụng để giải quyết bài toán. Giải thuật Tabu cho bài toán cân bằng dây chuyền sản xuất dạng 2 như sau: Bước 1: Nhập dữ liệu (Tổng công việc thành phần; Tabu size; số bước lặp lớn nhất maxiter; thời gian gia công của từng công việc thành phần; số trạm làm việc cho trước n; ma trận quan hệ tiên quyết M). Trong bước này, những dữ liệu và các thông số của giải thuật sẽ được lần lượt đưa vào chương trình mày tính. Trong đó: tổng công việc thành phần là tất cả những công đoạn cần thiết cho quá trình lắp ráp; Tabu size: tham số dùng để cập nhật tabu list trong việc chấp nhận di chuyển khi công việc thành phần chuyển từ trạm này sang trạm khác; số bước lặp là thông số dùng để dừng giải thuật (từ 100 – 1000 lần); thời gian gia công là thời gian cụ thể của từng công đoạn trong quá trình lắp ráp sản xuất; số trạm làm việc cho trước là số trạm thực tế đã có của dây chuyền cũ, ma trận quan hệ tiên quyết có được từ quy trình công nghệ dùng để xác định trật tự lắp ráp của sản phẩm. Bước 2: Lời giải ban đầu (Biến nhớ Tabu; xác định ma trận MT bằng thuật toán Warshall; xây dựng lời giải khả thi ban đầu bằng cách phân bổ tất cả các công việc thành phần vào 1 trạm; xác định giá trị hàm mục tiêu ban đầu và phân bổ vào biến CurObj và BestObj). Biến nhớ Tabu là biến nhớ dùng để giúp giải thuật thoát khỏi vòng lặp tối ưu cục bộ; ma trận MT dùng thuật toán Warshall giúp thỏa mãn điều kiện của biểu đồ quan hệ tiên quyết khi thực hiện bài toán cân bằng; xây dựng lời giải ban đầu chỉ có 01 trạm; xác định giá trị hàm mục tiêu cho bài toán này gán vào biến CurObj và BestObj. Bước 3: Cho i từ 1 đến maxiter, thực hiện bước 4, chuyển sang bước 5 khi thực hiện xong. Bước 4: Thực hiện chương trình con “moving” để xác định di chuyển tiếp theo; (Thực hiện di chuyển; cập nhật biến nhớ Tabu; cập nhật biến CurObj; nếu CurObj tốt hơn BestObj thì cập nhật lời giải tốt nhất bằng cách copy lời giải hiện tại vào lời giải tốt nhất, hay gán BestObj := CurObj). Bước này là bước chính của giải thuật, việc thực hiện di chuyển để đảm bảo các công đoạn có thể phân bổ tự do để chúng ta tìm được vị trí phân bổ tốt nhất; cập nhật bộ nhớ và các biến để đảm bảo giá trị hàm mục tiêu được cải thiện đồng thời đảm bảo giá trị cũng như lời giải tốt nhất của giải thuật sẽ được lưu giữ và truy xuất kết quả khi giải thuật kết thúc ở bước 5. Bước 5: Thoát khỏi giải thuật và đưa ra lời giải tốt nhất khi thực hiện hết maxiter bước lặp. 3.3.Thay đổi lời giải ban đầu kết hợp với điều kiện cải thiện lời giải Để nghiên cứu hoàn chỉnh hơn cho thuật toán Tabu đối với bài toán cân bằng dây chuyền sản xuất tổng quát, trong nghiên cứu này, tác giả sẽ xem xét điều kiện cải thiện lời giải kết hợp với thay đổi lời giải ban đầu và so sánh kết quả với những công trình đã nghiên cứu trước đây, phần này nhằm tổng kết giải thuật Tabu. Kết quả nghiên cứu được công bố 10 trên Tạp chí Khoa học Trường Đại học Mở Tp. Hồ Chí Minh số 2(30) số ra tháng 03 năm 2013 (có GIẤY XÁC NHẬN đính kèm). Theo thuật toán Tabu được trình bày trong phần cơ sở lý thuyết (chương 2), tác giả sẽ xem xét thay đổi điều kiện lời giải ban đầu, cụ thể như sau: 3.3.1. Lời giải ban đầu: Theo kinh nghiệm của những nghiên cứu trước thì lời giải ban đầu được hình thành theo nguyên tắc công việc (công đoạn) theo sau nhiều nhất, trong nghiên cứu này cách này gọi là phương pháp 1. Ngoài ra để so sánh và đánh giá, nghiên cứu dùng cách xây dựng lời giải đầu đơn giản hơn bằng cách phân bổ mỗi công việc vào một trạm làm việc, cách này được gọi là phương pháp 2. phương pháp 2 này này đơn giản hóa việc cấp lời giải đầu cho giải thuật, đơn giản hóa tính toán của giải thuật, tạo ra lời giải khả thi trực tiếp. Kết quả của nghiên cứu được so sánh và trình bày trong chương 4. 3.3.2. Điều kiệu cải thiện lời giải Như đã trình bày trong chương 2 của báo cáo, nghiên cứu này tác giả cũng sử dụng 2 hình thức cải thiện để thực hiện giải thuật Tabu cho bài toán tổng quát đó là: i) chấp nhận di chuyển đến tập lời giải mới khi tìm được lời giải cải thiện đầu tiên (first improvement – được gọi là nguyên tắc 1), nguyên tắc này không tìm hết tập lời giải hiện tại, dừng việc tìm kiếm và chấp nhận di chuyển khi tìm được lời giải đầu tiên cải thiện hơn lời giải đang có; ii) chấp nhận di chuyển khi toàn bộ tập lời giải hiện tại được khảo sát hết, và lời giải cải thiện nhất sẽ được chọn để thay thế lời giải tốt nhất (best improvement – được gọi là nguyên tắc 2). Cả hai nguyên tắc đều được khảo sát và so sánh kết quả trong chương 4 của báo cáo. 3.4. Một số sơ đồ khối của giải thuật Trong phần này, nghiên cứu sẽ trình bày một số sơ đồ khối để minh họa cho giải thuật của nghiên cứu như sau: Sơ đồ 3.1 trình bày thuật toán Tabu theo nguyên tắc 1, sơ đồ khối này thể hiện cách thức thực hiện chương trình máy tính để giải bài toán cân bằng dây chuyền sản xuất tổng quát theo nguyên tắc 1. Sơ đồ 3.2 trình bày việc kiểm tra và chấp nhận di chuyển theo nguyên tắc 1, sơ đồ này là chương trình con của thuật toán Tabu theo nguyên tắc 1 để chấp nhận một di chuyển mới nhằm thay đổi lời giải và tạo ra tập lời giải mới. Sơ đồ 3.3 trình bày thuật toán Tabu theo nguyên tắc 2, sơ đồ khối này thể hiện cách thức thực hiện chương trình máy tính để giải bài toán cân bằng dây chuyền sản xuất tổng quát theo nguyên tắc 2. Sơ đồ 3.4 trình bày việc kiểm tra và chấp nhận di chuyển theo nguyên tắc 2, đây là chương trình con của thuật toán Tabu theo nguyên tắc 2, chương trình này đảm bảo thực hiện việc tìm kiếm trên toàn bộ tập lời giải hiện tại, để tìm lời giải tốt nhất trước khi chấp nhận di chuyển. 11 12 13 14 15 CHƯƠNG 4 KẾT QUẢ NGHIÊN CỨU 4.1. Kết quả nghiên cứu đối với bài toán cân bằng dây chuyền sản xuất dạng 2 Từ giải thuật được trình bày trong chương 3, nghiên cứu cũng xác định được những kết quả nhất định. Các nhóm kết quả được kiểm định với một số công trình đã được đăng trên các tạp chí để làm cơ sở củng cố độ tin cậy của giải thuật. Trong phần này, từng nhóm kết quả tương ứng với từng giải thuật 1 & 2 được trình bày trong các bảng sau: Bảng 4.1: Kết quả nghiên cứu theo giải thuật 1 Bài toán Số trạm Giá trị chặn dưới Giá trị tối ưu (LINGO) Kết quả n C Bowman 8 công đoạn 2 3 4 5 6 38 25 19 15 13 38 28 22 17 17 2 3 4 5 5 38 28 22 17 17 Hopfield 8 công đoạn 2 3 4 5 6 69 46 35 28 23 69 47 36 34 34 2 3 4 5 5 69 47 36 34 34 Hoffman 9 công đoạn 2 3 4 5 6 19 13 10 8 7 19 13 10 9 8 2 3 4 5 6 19 13 10 9 8 Dar-el 11 công đoạn 2 3 4 5 6 93 62 47 37 31 93 62 48 45 45 2 3 4 5 5 93 62 48 45 45 2 3 4 5 6 7 23 16 12 10 8 7 23 16 12 10 9 8 2 3 4 5 6 7 23 16 12 10 9 8 2 3 4 5 6 7 200 134 100 80 67 58 200 137 102 90 70 70 2 3 4 5 6 6 200 137 102 90 70 70 Jackson 11 công đoạn Kilbridge - Wester 12 công đoạn 16