đặt vấn đề, mục tiêu của luận văn, phạm vi giới hạn của luận văn, nội dung luận văn, các nghiên cứu liên quan đến đề tài và cuối cùng là phần cấu trúc tổng quát của luận văn. 3 - Chương 2: Cơ sở lý thuyết. Chương này sẽ trình bày về các khái niệm, lý thuyết cơ sở liên quan đến đề tài nghiên cứu với các nội dung nghiên cứu. Trong luận văn này, tôi xin trình bày 2 lý thuyết liên quan đó là: • Điều độ cơ bản trong mô hình job shop.
• Dùng giải thuật di truyền để giải bài toán mục tiêu cực tiểu thời gian hoàn thành cực đại trong môi trường job shop. - Chương 3: Phân tích hiện trạng và xác định vấn đề. Đây là chương trọng tâm của luận văn. Phân tích việc điều độ thông qua các dữ liệu thu thập như số lượng, đơn hàng, máy móc và nhận xét.
- Chương 4: Áp dụng giải thuật di truyền cho bài toán điều độ trong mô hình job shop. Trong chương này sẽ trọng tâm xây dựng lời giải hàm mục tiêu và các biến vào giải thuật di truyền. - Chương 5: Kết luận. Chương này sẽ tổng kết lại các kết quả mà luận văn đã thực hiện được và phương hướng mở rộng.
4 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN 2.1 Lý thuyết điều độ cơ bản Nguồn tài nguyên thường được đề cập trong điều độ sản xuất là máy móc. Một máy móc có thể diễn tả bằng một phòng khách sạn hay một chiếc xe hơi, vv… Mỗi thực thể được gia công trên một máy gọi là công việc (job). Một công việc có thể là một thao tác riêng biệt hay là một tập hợp các thao tác trong quá trình sản xuất. Trong điều độ có sáu loại mô hình như sau là: - Mô hình điều độ dự án - Mô hình điều độ job shop - Mô hình hệ thống sản xuất nâng chuyển tự động - Mô hình điều độ hàng theo loạt - Mô hình hệ thống đặt chỗ trước và lập thời gian biểu - Mô hình điều độ nguồn nhân lực Trong đó có bốn loại hình điều độ cơ bản nhất là: - Mô hình một máy - Mô hình máy song song - Mô hình hình flow shop - Mô hình job shop [1] Mô hình job shop là mô hình sản xuất / dịch vụ mà mỗi công việc có một đường đi riêng biệt qua những máy hoặc thiết bị khác nhau như hình 2.
Job shop là tổng quát hoá của flow shop, một flow shop là một job shop mà trong đó mỗi công việc có một đường đi riêng. Một bài toán điều độ job shop tổng quát với n công việc và m máy. Mỗi công việc được thực hiện bởi một số máy cho trước và không chu trình. Mục tiêu của bài toán là cực tiểu makespan (Cmax) 5 Hình 2.1: Mô hình job shop 2.
Lý thuyết giải thuật di truyền Thuật toán di truyền gồm có bốn quy luật cơ bản là: - Lai ghép. - Chọn lọc tự nhiên. Quy trình lai ghép (phép lai): Quá trình này diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha-mẹ để hình thành nhiễm sắc thể mới mang đặc tính của cả cha lẫn mẹ. Phép lai này có thể mô tả như sau: - Chọn ngẫu nhiên hai hay nhiều cá thể trong quần thể.
Giả sử chuỗi nhiễm sắc thể của cha và mẹ đều có chiều dài là m. - Tìm điểm lai bằng cách tạo ngẫu nhiên một con số từ 1 đến m-1. Như vậy, điểm lai này sẽ chia hai chuỗi nhiễm sắc thể cha-mẹ thành hai nhóm nhiễm sắc thể con là m1 và m2. Hai chuỗi nhiễm sắc thể con lúc này sẽ là m11+m22 và m21+m12.
- Đưa hai chuỗi nhiễm sắc thể con vào quần thể để tiếp tục tham gia quá trình tiến hóa. - Quá trình đột biến (phép đột biến). Quá trình tiến hóa được gọi là quá trình đột biến khi một hoặc một số tính trạng của con không được thừa hưởng từ hai chuỗi nhiễm sắc thể cha-mẹ. Phép đột biến xảy 6 ra với xác suất thấp hơn rất nhiều lần so với xác suất xảy ra phép lai.
Phép đột biến có thể mô tả như sau: - Chọn ngẫu nhiên một số k từ khoảng 1 ≥ k ≥ m. - Thay đổi giá trị của gen thứ k. - Đưa nhiễm sắc thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn).
Phép tái sinh: là quá trình các cá thể được sao chép dựa trên độ thích nghi của nó. Độ thích nghi là một hàm được gán các giá trị thực cho các cá thể trong quần thể của nó. Phép tái sinh có thể mô phỏng như sau: - Tính độ thích nghi của từng cá thể trong quần thể, lập bảng cộng dồn các giá trị thích nghi đó (theo thứ tự gán cho từng cá thể) ta được tổng độ thích nghi. Giả sử quần thể có n cá thể.
Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i là Ft. Tổng độ thích nghi là Fm. - Tạo số ngẫu nhiên F có giá trị trong đoạn từ 0 đến Fm. - Chọn cá thể k đầu tiên thỏa mãn F ≥ Ft đưa vào quần thể của thế hệ mới.
- Phép chọn: là quá trình loại bỏ các cá thể xấu và để lại những cá thể tốt. Phép chọn được mô tả như sau: Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần. Loại bỏ các cá thể cuối dãy, chỉ để lại n cá thể tốt nhất. Tổng hợp lại các bước áp dụng giải thuật di truyền như sau: 7 Hình 2.2: Sơ đồ giải thuật di truyền 2.
Nghiên cứu liên quan lĩnh vực điều độ trong luận văn. Điều độ nói chung và điều độ trong mô hình job shop nói riêng được xem là một vấn đề khó trong việc tìm ra các lời giải tối ưu trong điều kiện thế giới thực. Trong điều độ có n công việc hữu hạn và m tập hợp máy và được xử lý theo thời gian và thứ tự nhất định, mục tiêu là giảm thiểu tổng thời gian cần thiết để hoàn thành cho tất cả công việc. Đã có nhiều nghiên cứu về các giải thuật với mục đích để giải bài toán này.
Những giải thuật đó là giải thuật tabu search, giải thuật tối ưu hoá đàn kiến (Ant colony optimization), giải thuật đàn ong nhân tạo (Artificial bee colony)…Mỗi giải thuật đều có ưu điểm và nhược điểm riêng, tuỳ vào vấn đề hiện tại cũng như yêu cầu của người giải quyết vấn đề mà ta sẽ sử dụng giải thuật thích hợp. Trong phạm vi luận văn này, vì giải thuật di truyền được dùng để tiếp cận vấn đề này nên ta chỉ tập trung các đề tài nghiên cứu về giải thuật di truyền. Thông thường trong bài toán điều độ, mục tiêu là giảm thời gian của toàn bộ chương trình sản xuất, giảm thiểu độ trễ trung bình, tối đa hóa tải trọng của máy móc, hoặc trung bình có trọng số của nhiều tiêu chí tương tự [2]. Trong vô số các vấn đề về lập kế hoạch sản xuất, vấn đề tổng quát về mô hình job shop là vấn đề có 8 nhiều nghiên cứu và nó khó giải quyết.
Bài toán điều độ job shop cổ điển có thể được phát biểu như sau: có m máy khác nhau và n công việc khác nhau được lên lịch. Mỗi công việc bao gồm một tập hợp các thao tác và thứ tự vận hành trên máy được xác định trước. Mỗi hoạt động được đặc trưng bởi máy yêu cầu và thời gian xử lý cố định. Có một số giả định được đưa ra khi giải quyết các vấn đề về lập lịch trình của cửa hàng việc làm, chẳng hạn như [3]: (1) mỗi máy là một thực thể riêng; (2) không cho phép ưu tiên; (3) chỉ có một trong mỗi loại máy; (4) các ràng buộc về công nghệ đã được biết trước và là bất biến; và (5) không có ngẫu nhiên, tất cả dữ liệu đều được biết và cố định.
Và có một số ràng buộc đối với các công việc và máy móc, như sau [4]: (1) một công việc không truy cập cùng một máy hai lần, (2) không có ràng buộc ưu tiên giữa các hoạt động của các công việc khác nhau, (3) một hoạt động không thể bị gián đoạn, (4) mỗi máy chỉ có thể xử lý một công việc tại một thời điểm, (5) không xác định thời gian phát hành cũng như ngày đến hạn. Vấn đề là xác định trình tự hoạt động trên ứng dụng của thuật toán di truyền cho các vấn đề lập lịch cho mô hình job shop được các nhà nghiên cứu Yamada và Nakano báo cáo [5, 6]. Các công trình cụ thể về việc sử dụng thuật toán di truyền cho các vấn đề lập lịch điều độ trong môi trường job shop dựa trên quy trình sản xuất đã được trình bày bởi Fang và cộng sự. Trong [9] của đồng tác giả Yong Ming Wang và Hong Li Yin đã giới thiệu cách để mã hoá các chuỗi gen để tính toán hàm mục tiêu cực tiểu thời gian trễ cực đại trong mô hình job shop.
Tác giả Brahtiba [10] đã dùng phương pháp chọn lọc Roulette Wheel Section để chọn ra các lời giải sau khi các lời giải đã được xác định bằng hàm Fitness. Brucker và Kampmeyer [11] đã trình bày một khuôn khổ chung để mô hình hóa và giải quyết các vấn đề lập lịch theo chu kỳ. Phương pháp luận Xác Tiếp Hiểu rõ các đối tượng nghiên cứu: thời gian bắt đầu, Mục thời gian gia công, số lượng của đơn hàng và quy trình định cận đích gia công, ngày giao hàng. vấn đề đối 9 tượng Quan sát và thu thập số liệu: xuống xưởng sản xuất trực tiếp quan sát sản phẩm và các trạm gia công, đồng thời Phương hỏi ý kiến chuyên gia và xem xét số liệu từ các bộ phân pháp liên quan là quản lý sản xuất, kế hoạch sản xuất, bộ phận kỹ thuật, bộ phận xuất hàng.
Thông tin đối tượng nghiên cứu: thời gian bắt đầu, thời Đầu ra gian gia công, số lượng của đơn hàng và quy trình gia công của từng đơn hàng, chi phí sản xuất của đơn hàng. Mục Xác định vấn đề hiện tại của đối tượng đã nêu trên. đích Phân tích Trao đổi, thảo luận với các bộ phận liên quan để lấy số Phương liệu gồm: Bảng kiểm kê cuối tháng, bảng kế hoạch. hiện pháp trạng Đầu ra Thời gian hoàn thành các đơn hàng.
Mục Xác định những nhân tố tạo ra vấn đề trên. đích Phân Phương Xem xét các mô hình điều độ đã được học để xác định tích pháp mô hình hiện tại trong công ty.
