The maximally diverse grouping problem (MDGP) seeks to partition the vertices of a complete graph into a fixed number of groups under capacity constraints, maximizing the sum of edge weights within each group. MDGP is an NP-hard combinatorial optimization problem and has wide real-world applications. In this paper, we propose an adaptive configuration-aware simulated annealing (ACSA) algorithm to solve MDGP. First, ACSA adopts a relaxation-based insertion strategy, which temporarily relaxes capacity constraints to expand the neighborhood and allow effective exploration of promising regions. Second, a memory-based swap mechanism is introduced to integrate high-potential suboptimal swap moves into the conventional best-swap operation, thereby achieving a better balance between diversification and intensification of the search. Finally, ACSA employs a vertex-wise sequential coordination strategy to dynamically organize the insertion and swap moves, which enhances the search flexibility. Experiments on 500 benchmark instances demonstrate the strong competitiveness of ACSA, as it improves the best results among the state-of-the-art algorithms on 460 instances and matches them on 39 instances.

The clique partitioning problem (CPP) aims to find a partition of vertices of a complete graph in order to maximize the sum of edge weights within each partition (clique), which has been proven to be NP-hard and has wide real-world applications. In this paper, we propose an elite-guided weighted simulated annealing algorithm called EWSA to solve the CPP. First, EWSA employs two specific configurations and alternates between them via an oscillation strategy, which balances the exploitation and exploration of the search. Second, a weighting strategy is introduced to improve the scoring function in traditional simulated annealing, which is able to guide the search to explore diverse solutions. Finally, a partition restriction strategy is adopted to reduce search space and increase the search efficiency. Experiments on 255 instances demonstrate the competitiveness of EWSA. For 130 open instances, EWSA discovers new upper bounds in 32 cases and matches the best known results for the others. For the remaining 125 closed instances, EWSA achieves the best known objective values within a short computational time.

The α-neighbor p-center problem (α-pCP) is an extension of the classical p-center problem. It aims to select p centers from a set of candidate centers to minimize the maximum distance between any client and its α service centers. In this paper, we propose a weighting-based fast local search algorithm called WFLS for solving α-pCP. First, WFLS converts the complex α-pCP into a series of decision subproblems by specifying the service radius, effectively mitigating the gradient vanishing issue during the search process, and introduces a new MIP model. Then, it addresses the simpliffed subproblems using a fast local search procedure with a swap-based neighborhood structure. WFLS adopts an efffcient weighting strategy, an incremental evaluation technique, a reffned-grained penaltybased neighborhood evaluation, and two scoring functions of neighborhood evaluation to accelerate and guide the search process. Computational experiments on 154 widely used public benchmark instances demonstrate that WFLS outperforms the state-of-the-art methods in the literature. Speciffcally, WFLS improves 69 previous best known results and matches the best know results for all the remaining ones in less time than other competitors.

Large Language Models (LLMs) have emerged as a promising technology for solving combinatorial optimization problems. However, their direct application to scheduling problems remains limited due to the inherent complexity of these problems. This paper proposes an LLMs-based neighborhood search method that leverages LLMs to tackle the job shop scheduling problem (JSP) and its variants. The main contributions of this work are threefold. First, we introduce a novel LLMs-guided neighborhood evaluation strategy that guides local search by dynamically adjusting operation weights. Second, we develop a verification evolution (VeEvo) framework to mitigate the hallucination effects of LLMs, enabling the generation of high-quality heuristics for weight updates. Third, we integrate this framework with the weighted neighborhood evaluation strategy to effectively guide the search towards promising regions. Extensive experiments are conducted on 349 benchmark instances across three classical scheduling problems. The results demonstrate that our algorithm significantly outperforms existing state-of-the-art methods. For JSP, our algorithm reduces the average optimality gap from 10.46% to 1.35% on Taillard's instances compared to reinforced adaptive staircase curriculum learning. For flexible JSP (FJSP), it reduces the gap from 13.24% to 0.05% on Brandimarte's instances compared to deep reinforcement learning methods. Furthermore, for FJSP with sequence dependent setup time, our algorithm updates 9 upper bounds for benchmark instances.

The single row facility layout problem aims to position a set of facilities of given lengths on a single line so as to minimize the weighted sum of the distances between all the pairs of facilities, which has wide real-world applications in planning areas. In this paper, we propose an oscillation based simulated annealing algorithm for solving the single row facility layout problem. Our algorithm dynamically oscillates between two simulated annealing algorithms. One employs an exponential descent insertion strategy to capture effective movements, which increases the search efficiency, while the other adopts a radius-constrained neighborhood structure to reduce search space, which significantly enhances the intensification of the search. Besides, a new fast incremental evaluation method based on decomposition and recombination is adopted to speed up the search. Experiments on 110 instances demonstrate the competitiveness of our algorithm. In specific, for all the 110 instances, our algorithm discovers new upper bounds in 32 cases and matches the best known results for other 75 instances, only remaining 3 worse results.

This article studies the two-dimensional (2-D) rectangle packing area minimization problem (RPAMP), a key subproblem in floor planning for very large-scale integration (VLSI) chip design. The goal of RPAMP is to orthogonally pack a set of rectangles into a variable-sized rectangular container without overlap, while minimizing the area of the container. By transforming the original problem into a series of 2-D strip packing problems (2DSPs), we propose a two-stage adaptive search algorithm (TS-ASA) to tackle the RPAMP. TS-ASA incorporates several distinctive features: First, a new candidate width pruning strategy is introduced, which limits the number of rectangles used for width combinations, thus reducing the search space. Second, the packing process is divided into two stages, with distinct scoring rules for each stage to optimize space utilization. Additionally, a multirestart strategy is employed to identify the appropriate switching point for the scoring rules. Tested on 39 public benchmark instances and compared with existing state-of-the-art algorithms, TS-ASA improves the best-known solutions for 27 instances and matches the best results for two instances. The experimental results demonstrate the effectiveness and efficiency of the proposed TS-ASA.

Multi-depot vehicle routing problem (MDVRP) is a variant of the classical VRP, which includes several depots with a fleet of homogeneous vehicles to serve each customer exactly once while satisfying the vehicle capacity and duration constraints. We propose a memetic algorithm called GVTS-DPX which hybridizes the granular variable tabu search (GVTS) with the depot partition crossover (DPX) for solving the MDVRP, where GVTS combines tabu search and the granular neighborhoods with variable neighborhood descent, while DPX treats the solution as the collection of depots and partitions the depots into two groups covering the most customers. The main contributions of this study include proposing the DPX operator, reforming several existing move types used for the VRP and its variants, and designing a granular variable neighborhood consisting of a total of 21 kinds of move types. Experimental results on 33 public MDVRP instances indicate that GVTS-DPX is competitive with the state-of-the-art algorithms in the literature.

Improving productivity at the expense of heavy energy consumption is often no longer possible in modern manufacturing industries. Through efficient scheduling technologies, however, we are able to still maintain high productivity while reducing energy costs. This article addresses a flexible job shop scheduling problem under time-of-use electricity tariffs with the objective of minimizing total energy consumption while considering a predefined makespan constraint. We propose a novel two-individual-based evolutionary (TIE) algorithm, which incorporates several distinguishing features, such as a tabu search procedure, a topological order-based recombination operator, a new neighborhood structure for this specific problem, and an approximate neighborhood evaluation method. Extensive experiments are conducted on widely used benchmark instances, which show that the proposed TIE outperforms traditional trajectory-based and population-based methods. We also analyze the key features of TIE to identify its critical success factors, and discuss the impact of varying key parameters of the problem to derive practical insights.

Population-based evolutionary algorithms usually manage a large number of individuals to maintain the diversity of the search, which is complex and time-consuming. In this paper, we propose an evolutionary algorithm using only two individuals, called master-apprentice evolutionary algorithm (MAE), for solving the flexible job shop scheduling problem (FJSP). To ensure the diversity and the quality of the evolution, MAE integrates a tabu search procedure, a recombination operator based on path relinking using a novel distance definition, and an effective individual updating strategy, taking into account the multiple complex constraints of FJSP. Experiments on 313 widely-used public instances show that MAE improves the previous best known results for 47 instances and matches the best known results on all except 3 of the remaining instances while consuming the same computational time as current state-of-the-art metaheuristics. MAE additionally establishes solution quality records for 10 hard instances whose previous best values were established by a well-known industrial solver and a state-of-the-art exact method.