Zhang P, Song S, Niu S, Zhang R. A Hybrid Artificial Immune-Simulated Annealing Algorithm for Multiroute Job Shop Scheduling Problem With Continuous Limited Output Buffers.
IEEE TRANSACTIONS ON CYBERNETICS 2022;
52:12112-12125. [PMID:
34133309 DOI:
10.1109/tcyb.2021.3081805]
[Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/12/2023]
Abstract
In this article, we study the multiroute job shop scheduling problem with continuous-limited output buffers (MRJSP-CLOBs). In contrast to the standard job shop scheduling problem (JSP), continuous-limited output buffers render the commonly used graph-based approaches inapplicable, and the multiroute issue further increases computational complexity. To this end, we formulate MRJSP-CLOB as a mixed-integer linear program (MILP), which is typically NP-hard. Then, we extend the critical block in the JSP by utilizing the no-time-gap relationship and design a new neighborhood structure. Furthermore, we propose a hybrid artificial immune-simulated annealing algorithm (AIA-SA) by sharing iterations and integrating a random infeasible solution repairing algorithm with a new SA acceptance rule, which enables individuals to share information and increases the robustness of the corresponding SA parameters. Finally, the AIA-SA is compared with CPLEX and state-of-the-art algorithms on MRJSP-CLOB with different sizes. Experiments for large-sized instances demonstrate that our algorithm requires less than 3% computing time of the CPLEX, while being faster and more accurate than the other algorithms.
Collapse