Giảm thiểu Thời gian Hoàn thành Trung bình trong Hệ thống Xử lý BATCH

Chúng tôi xem xét các công việc xử lý theo lô để giảm thiểu thời gian hoàn thành trung bình. Một máy xử lý theo lô có thể xử lý đồng thời tối đa $B$ công việc. Mỗi công việc được đại diện bởi thời gian đến và thời gian xử lý. Các công việc được xử lý trong một lô có cùng thời gian hoàn thành, tức là thời gian bắt đầu chung của chúng cộng với thời gian xử lý của công việc dài nhất. Đối với xử lý theo lô, thường yêu cầu lên lịch không thể tạm dừng, và chúng tôi thảo luận về trường hợp này. Vấn đề xử lý theo lô giảm xuống vấn đề lập lịch hệ thống đơn xử lý thông thường nếu $B=1$. Chúng tôi tập trung vào trường hợp cực đoan khác là $B=+\infty$. Ngay cả đối với trường hợp cực đoan có vẻ đơn giản này, chúng tôi có thể chỉ ra rằng vấn đề là NP-khard đối với phiên bản có trọng số. Ngoài ra, chúng tôi thiết lập một thuật toán thời gian đa thức cho một trường hợp đặc biệt khi chỉ có một số lượng cố định các thời gian xử lý công việc. Cuối cùng, chúng tôi đưa ra một sơ đồ xấp xỉ thời gian đa thức cho trường hợp tổng quát.