Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán di truyền cho việc lập lịch công việc vào lại trên các máy song song với một máy chủ từ xa
Tóm tắt
Bài báo này xem xét một vấn đề lập lịch công việc vào lại trên các máy chính song song với một máy chủ từ xa, được yêu cầu thực hiện hoạt động thiết lập. Trong vấn đề này, mỗi công việc có ba hoạt động. Hai hoạt động đầu tiên và cuối cùng được thực hiện bởi cùng một máy chính, cho thấy sự quay lại, và hoạt động thứ hai được xử lý trên máy chủ đơn. Thứ tự các công việc được xác định trước trong bối cảnh của chúng tôi. Thách thức là phân công công việc cho các máy chính để giảm thiểu thời gian hoàn thành công việc. Chúng tôi phát triển một thuật toán di truyền (GA) để giải quyết vấn đề này. Dựa trên một chiến lược đơn giản để phân công công việc theo lô trên các máy chính song song, việc biểu diễn vector khóa ngẫu nhiên chuẩn hóa được sử dụng để chia nhỏ các công việc thành các lô. So sánh giữa thuật toán đề xuất, thuật toán nhánh và ranh giới (BB) và thuật toán heuristic, lập lịch phối hợp (CS), đây là một trong những thuật toán heuristic duy nhất để giải quyết vấn đề này trong tài liệu, được thực hiện trên dữ liệu chuẩn. Các thí nghiệm tính toán cho thấy rằng thuật toán di truyền đề xuất vượt trội hơn so với thuật toán heuristics CS và tỷ lệ cải tiến tương đối tối đa trong thời gian hoàn thành công việc là 1,66%.
Từ khóa
Tài liệu tham khảo
Abdekhodaee A H, Wirth A. Scheduling parallel machines with a single server: Some solvable cases and heuristics[J]. Computers and Operations Research, 2002, 29(3): 295–315.
Abdekhodaee A H, Wirth A, Gan H S. Scheduling two parallel machines with a single server: The general case[J]. Computers and Operations Research, 2006, 33(4): 994–1009.
Allahverdi A, Ng C T, Cheng T C E et al. A survey of scheduling problems with setup times or costs[J]. European Journal of Operational Research, 2008, 187(3): 985–1032.
Zhang L, Wirth A. On-line scheduling of two parallel machines with a single server[J]. Computers and Operations Research, 2009, 36(5): 1529–1553.
Huang S M, Cai LN, Zhang X Y. Parallel dedicated machine scheduling problem with sequence dependent setups and a single server[J]. Computers and Industrial Engineering, 2010, 58(1): 165–174.
Guo Shouwei, Kang Liying. Online scheduling of malleable parallel jobs with setup times on two identical machines[J]. European Journal of Operational Research, 2010, 206(3): 555–561.
Gan H S, Wirth A, Abdekhodaee A. A branch-and-price algorithm for the general case of scheduling parallel machines with a single server[J]. Computers and Operations Research, 2012, 39(9): 2242–2247.
Turker A K, Sel C. Scheduling two parallel machines with sequence-dependent setups and a single server[J]. Gazi University Journal of Science, 2011, 24(1): 113–123.
Kim M Y, Lee Y H. MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server[J]. Computers and Operations Research, 2012, 39(11): 2457–2468.
Wang G, Cheng T C E. An approximation algorithm for parallel machine scheduling with a common server[J]. Journal of the Operational Research Society, 2001, 52(2): 234–237.
Wang M Y, Sethi S P, van de Velde S L. Minimizing makespan in a class of re-entrant shops[J]. Operations Research, 1997, 45(5): 702–712.
Chakhlevitch H, Glass C A. Scheduling reentrant jobs on parallel machines with a remote server[J]. Computers and Operations Research, 2009, 36(9): 2580–2589.
Holland J H. Adaptation in Natural and Artificial Systems[M]. The University of Michigan Press, Ann Arbor, 1975.
Davis L. Handbook of Genetic Glgorithms[M]. Van Nostrand, New York, 1991.
Abdelmaguid T F. Representations in genetic algorithm for the job shop scheduling problem: A computational study[J]. Journal of Software Engineering and Applications, 2010, 3(12): 1155–1162.
Benchmark Data [EB/OL]. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/HybridReentrantShop01.html.