Bài toán lập kế hoạch sản xuất với các công việc xung đột lẫn nhau

Tóm tắt

Xuất phát từ các ứng dụng trong thực tế, chúng tôi nghiên cứu bài toán lập kế hoạch sản xuất trong đó các công việc có thể bị xung đột khi thực hiện cùng thời điểm trên các máy khác nhau, và có sự ràng buộc về mặt thời gian. Cụ thể, chúng ta cần phân chia các công việc để xử lý trên các máy giống nhau. Các công việc này có thời gian xử lý giống nhau, nhưng một số có thể bị xung đột khi được thực hiện cùng thời điểm. Tất cả các máy bắt đầu hoạt động cùng lúc và phải kết thúc tại một thời điểm cho trước. Do giới hạn về mặt thời gian nên sẽ có thể có một số công việc không được xử lý. Yêu cầu đặt ra là cần tìm một số lượng lớn nhất công việc có thể xử lý được. Trong bài báo này, chúng tôi đưa ra hai kết quả NP-khó cho bài toán được nghiên cứu trong trường hợp nhóm các công việc xung đột có kích thước tối đa bằng . Chúng tôi cũng thảo luận một số câu hỏi mở, có thể là các hướng nghiên cứu tiếp theo trong tương lai.