In a local search algorithm, one of its most important features is the definition of its neighborhood which is crucial to the algorithm’s performance. In this paper, we present an analysis of neighborhood combination search for solving the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness (SMSWT). First, We propose a new neighborhood structure named Block Swap (B1) which can be considered as an extension of the previously widely used Block Move (B2) neighborhood, and a fast incremental evaluation technique to enhance its evaluation efficiency. Second, based on the Block Swap and Block Move neighborhoods, we present two kinds of neighborhood structures: neighborhood union (denoted by B1
- Article type
- Year
- Co-author
An agile earth-observing satellite equipped with multimode cameras capable of transmitting observation data to other satellites is developed to rapidly respond to requests with multiple observation modes. This gives rise to the Multisatellite Multimode Crosslink Scheduling (MMCS) problem, which involves allocating observation requests to agile satellites, selecting appropriate timing and observation modes for the requests, and transmitting the data to the ground station via the satellite communication system. Herein, a mixed integer programming model is introduced to include all complex time and operation constraints. To solve the MMCS problem, a two-stage heuristic method, called Fast insertion Tabu Search with Conflict-avoidance (FTS-C) heuristic, is developed. In the first stage, a conflict-avoidance insertion algorithm is designed to generate a high-quality initial solution by considering the requests transmission and download. Further, the tabu search-based second stage optimizes the initial solution. Finally, an extensive empirical study based on a real-world situation demonstrates that FTS-C can generate a solution with higher quality in less time than other state-of-the-art algorithms and the CPLEX solver.