Chương 1: Giới thiệu tổng quan và các nghiên cứu liên quan. - Chương 2: Giới thiệu các phương pháp heuristic. - Chương 3: Cài đặt thử nghiệm - Chương 4:Mô phỏng và kết luận 6 CHƯƠNG 2: TỔNG QUAN VÀ CÁC PHƯƠNG PHÁP HEURISTIC 2. Tổng quan về bài toán tối ưu trong sản xuất và bàn toán CF 2.1 Tổng quan về bài toán tối ưu trong sản xuất Ngày nay, trong sản xuất, vấn đề tối ưu là sự sống còn của một doanh nghiệp.
Do tính cạnh tranh, nguồn lực có hạn nên thời gian hoàn thành sản phẩm hay dịch vụ phải nhanh chóng để đáp ứng theo kịp nhu cầu của khách hàng. Theo lịch sử, ngành công nghiệp đã trải qua ba giai đoạn tương ứng với ba thời kì công nghệ, đặc biệt ngày nay có sự can thiệp của ngành công nghệ thông tin. Lần lượt các giai đoạn là: - Giai đoạn Cost Focus: từ thế kỷ 18 đến những năm 1980: Tập trung vào chi phí (cost focus). Trong khoảng thời gian dài này, các định hướng trong sản xuất được ghi nhận thông qua những nghiên cứu định hướng như: công nhân chuyên nghiệp (labor specialization của ông Smith và Babbage), các thành phần sản xuất được chuẩn hóa thành các sản phẩm (standardized parts của ông Whitney).
Từ năm 1880 đến 1910: hàng loạt các lí thuyết về quản lý sản xuất được hình thành như: Gantt Charts (ông Gantt), Motion&Time Studies, Process Analysis, lý thuyết hàng đợi (của ông Erlang)…Từ năm 1910 đến 1980: kỷ nguyên sản xuất lượng hàng hóa cực lớn được xem bắt đầu. Khi đó, nhiều công cụ toán học được phát triển để đáp ứng với việc tối ưu trong sản xuất như: quy hoạch tuyến tính (của Dantzig), phân tích mẫu thống kê (của ông Shewhart),… - Giai đoạn Quality Focus: từ năm 1980 đến năm 1995 được xem là giai đoạn tập trung vào chất lượng (quality focus), nhiều giải pháp được công nghệ thông tin hóa như CAD (computer aided design), total quality management,… - Giai đoạn Customization focus: từ năm 1995 đến nay được xem là giai đoạn tập trung vào khách hàng (customization focus). Tính toàn cầu hóa, internet, các công cụ hoạch định tài nguyên doanh nghiệp (ERP) và đặc biệt là các xu hướng lập lịch quản lý tối ưu được đề ra nhằm giải quyết vấn đề mâu thuẫn 7 giữa nguồn lực bị giới hạn và số công việc hoàn thành. Nhìn chung, các đặc điểm của các bài toán vận hành phục vụ sản xuất luôn hướng đến các mục tiêu chung về: đảm bảo tài nguyên (do tài nguyên có thể ít hoặc không đáp ứng tức thời, tài nguyên có thể phục hồi hoặc không thể phục hồi); đảm bảo về số tác vụ (sẽ ảnh hưởng đến các nguồn lực khác như chi phí, tài nguyên, thời gian thực hiện); đảm bảo các ràng buộc (đây là điều kiện trong sản xuất để sản phẩm được đúng và đủ với yêu cầu); đảm bảo mục tiêu (đây là tiêu chí lựa chọn các phương án và phải được đảm bảo đạt được).
Từ những đặc điểm yêu cầu đó, các dạng bài toán về lập lịch (scheduling problems) được nhận diện và phát triển liên tục từ lý thuyết đến thực tế. Theo đó, trên lý thuyết, các bài toán lập lịch được phân thành nhiều loại, chủ yếu do giới hạn về tài nguyên. Theo nghiên cứu của J.1: Một số loại máy xử lý công việc được J. - Máy có thể hoạt động song song: máy đồng dạng (identical), máy cùng dạng (uniform), máy không liên quan.
- Mô hình đa tác vụ: Flow Shop, Open Shop, Job Shop, Mixed (hoặc Group) Shop, Multi-processor task sched. 8 Yếu tố việc β (job characteristics) - Các việc như nhau. - Các việc có liên hệ nhau theo một đồ thị không chu trình. - Các việc liên quan đến ngày hoàn thành.
- Thời gian xử lý các việc đều như nhau. - Thể hiện thời hạn sau cùng (deadline) của từng việc. - Các việc theo thứ tự (batching problem). - Các việc có thứ tự phụ thuộc thời gian khởi tạo.
- Các việc có yêu cầu hạn chế về máy (machine eligibility restrictions). - Các việc có tính chất hoán đổi trong dòng (permutation flow). - Các việc có tính chất nhóm (presence of blocking in flow). - Các việc không được chờ đợi (no-wait in flow).
- Các việc có tính lặp lại (recirculation in job). Yếu tố tối ưu γ thông thường liên quan đến: - Yếu tố thời gian - Yếu tố phạt lượng hóa theo số nguyên - Và các dạng tổ hợp tối ưu Để giải quyết các bài toán lập lịch, thông thường các mô hình tối ưu toán học và các mô hình tính toán gần đúng được phát triển. Các mô hình tối ưu toán học có ưu điểm chỉ ra được nghiệm chính xác. Tuy nhiên, với các bài toán kích thước dữ liệu lớn, các mô hình tính toán gần đúng sẽ có lợi ích về thời gian tìm nghiệm.
9 Bài toán tối ưu Các phương pháp giải chính xác LP, DP, BnB (nhánh-cận), MIP (Mixed Integer Programming – quy hoạch nguyên hỗn hợp) Các phương pháp giải gần đúng Approval algorithms Chỉ cần chứng minh được một phần tối ưu Hướng 1: giải được nhanh, đảm bảo được chất lượng theo ngưỡng cho trước ε Hướng 2: thuật giải theo thời gian (tùy thuộc tài nguyên): PTAS (Polygon Time Approximation Scheme – lược đồ xấp xỉ thời gian đa thức) Meta heuristics Bao gồm: - Genetic heuristics - Tabu search - Andy army: trên hệ thống vật lý - Giả lập dựa trên hình thái phát triển, xác định giải pháp tiến hóa Construction heuristics Bắt đầu với giải pháp rỗng và lặp đến giải pháp tốt nhất Sơ đồ 2.1: Các phương pháp tổng quát giải các bài toán tối ưu 2.2 Giới thiệu bài toán cell formation (CF) Được Flanders nêu từ năm 1925, lớp bài toán cellular manufacturing (CM) là ứng dụng về khái niệm công nghệ nhóm trong lĩnh vực công nghiệp. Sau đó, năm 1933 được Mitrofanov đề cập ở Nga và Burbidge đưa ra nhóm kỹ nghệ (group technology) vào thập kỷ 1970. Một trong những vấn đề gặp phải trong việc hiện 10 thực CM là bài toán cell formation (CFP). CFP là bài toán nhóm các máy móc (machine) và các bộ phận (part) trong các ô được sản xuất để tránh hoặc cực tiểu các phần tử ngoại lệ.
Một cách rõ ràng hơn, CM là hệ thống sản xuất có đặc điểm các bộ phận tương đồng được nhóm thành họ và các máy khác tính năng được gán vào các ô máy nhằm tăng hiệu quả về chi phí cho sản xuất nhiều sản phẩm cũng như uyển chuyển trong công tác điều hành sản xuất. Ưu việt chính của CM là giảm thời gian thiết lập, giảm thời gian ra sản phẩm, giảm thời gian sản xuất, giảm chi phí kho lưu trữ, tăng chất lượng, quản lý được tiến trình sản xuất , tăng tính uyển chuyển. Bài toán CF (CFP) là một trong những vấn đề chính yếu trong thiết kế của CM (theo Soleymanpour, Vrat và Shanker, 2002 [59]). Trong những năm sau này, nhiều phương pháp được phát triển để giải CFP.
Nghiên cứu chi tiết về các giải pháp được Joines, King và Culbreth (1996) [27], Selim, Askin và Vakharia (1998) [60] và Singh (1993) [61] đề cập. Ứng dụng của lớp bài toán này rất rộng. Ví dụ đối với sản xuất công nghiệp, như công nghệ sản xuất vi mạch, nhiều công đoạn hay thành phần/linh kiện có sự tương đồng cao trong thiết kế hay trong quy trình. Các công đoạn có sự tương đồng cao như thế thường được gom nhóm để tận dụng tối đa công suất của máy móc nhằm cực đại hóa hiệu quả tổng thể của hệ thống sản xuất.
Chi tiết hơn, xét một ví dụ khác, một robot thông minh được chế tạo để giải quyết các công việc giả định trong đường hầm. Khi làm việc thực tế, mỗi bộ phận của robot có thể làm số nhóm công việc nhiều nhất có thể. Vấn đề là hãy tối đa các công việc robot có thể làm cùng lúc. Theo đó, bài toán trên về điều khiển được phát biểu như sau: “Hệ thống sản xuất gồm m máy, sản xuất sản phẩm gồm n linh kiện ghép lại.
Bài toán đặt ra là tìm một giải pháp gồm K nhóm sao cho sự tương tác giữa các máy trong cùng nhóm và các linh kiện do các máy đó sản xuất ra là tối đa trong khi sự tương tác với các máy khác trong các nhóm khác là tối thiểu”.2: Minh họa việc nhóm các tiến trình Chi tiết hơn, theo bài báo của Iraj Mahdavi và cộng sự (2009) [1], mô hình bài toán được biểu diễn dạng toán học. Cụ thể là mô hình phi tuyến dựa trên ma trận liên hệ giữa máy-bộ phận với các biến nguyên. Theo đó, mô hình định hướng giảm các phần tử ngoại lệ (EE - exceptional elements) và số lượng các ô tránh (voids in cells) để đạt được tối ưu. EE được định nghĩa là những “số 1” nằm ngoài khối cụm đường chéo toàn “số 1”.
Và các “void” được định nghĩa là các ô “số 0” nằm bên trong khối cụm đường chéo toàn “số 1”. Chi tiết mô hình được phát biểu như sau: Tập các chỉ số: Gọi i: là chỉ số các bộ phận (parts): có P bộ phận nên i = 1.P j là chỉ số các máy (machines): có M máy nên j = 1.M k là chỉ số các ô (cells): có C máy nên k = 1.C Các tham số: Min_utk: cực tiểu đối với ô k. Ma trận sản xuất mang hai giá trị: 1 nếu bộ phận i được xử lý trên máy j, còn bộ phận i không xử lý trên máy j thì giá trị bằng 0. Các biến quyết định: 12 Hàm mục tiêu: Hoặc, hàm mục tiêu được viết như sau: Các ràng buộc về biến và giá trị của biến: Đảm bảo mỗi máy chỉ được gán cho một ô: (công thức 2) Đảm bảo mỗi bộ phận được gán cho một ô: (công thức 3) Đảm bảo mỗi ô xử lý được tối thiểu các (công thức 4) Để tương tác với các bài toán trong sản xuất, trải qua các giai đoạn nghiên cứu, một số định nghĩa được hình thành.
Cụ thể như sau: - Production: là việc tạo các sản phẩm hoặc các dịch vụ; 13 - Production management: là một chức năng tổ chức có chu kỳ trong công ty, bao gồm việc lập kế hoạch, dự báo và thực hiện marketing sản phẩm trong tất cả các giai đoạn của chu kỳ sản phẩm/dịch vụ. - Operation management: là các hoạt động tạo giá trị trong sản phẩm hoặc dịch vụ bằng việc chuyển đổi các đầu vào thành đầu ra. - Operation research: là các nguyên lý tường minh hỗ trợ ra quyết định. Đó là các ứng dụng, kỹ thuật toán học, các mô hình và các công cụ cho một bài toán trong hệ thống để tối ưu sản xuất.
