����ֱ��

M. Laguna, R. Martí, A. Martínez Gavara, S. Pérez-Peló, and M. G. C. Resende

This is a comprehensive review of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and its hybridization with Path Relinking (PR) over the past two decades. GRASP with PR has become a widely adopted approach for solving hard optimization problems since its proposal in 1999. The paper covers the historical development of GRASP with PR and its theoretical foundations, as well as recent advances in its implementation and application. The review includes a critical analysis of variants of PR, including memory-based and randomized designs, with a total of ten different implementations. It describes these advanced designs both theoretically and practically on two well-known optimization problems, linear ordering and max-cut. The paper also explores the hybridization of GRASP with PR and other metaheuristics, such as Tabu Search and Scatter Search. Overall, this review provides valuable insights for researchers and practitioners seeking to utilize GRASP with PR for solving optimization problems.

Laguna, M. and Martí, R. (1999) , INFORMS Journal on Computing, 11 (1), 899-1499.

Approximate dynamic programming for a dynamic appointment scheduling problem
Z. Nenova, M. Laguna, and D. Zhang

We study a dynamic appointment scheduling problem with cancellations and overbooking motivated by a medical clinic, where appointment requests arrive over time. The objective is to balance patient waiting time with service providers' overtime and idle time. The problem is formulated as a nite-horizon stochastic dynamic program. However, the formulation suers from the curse of dimensionality as the state is the service schedule, which is inherently high dimensional. We propose a solution approach based on approximate policy iteration and value function approximation. We validate the approach with data from a public hospital in the US. We use the data to develop a Weibull accelerated failure time model to estimate the time- and patient-dependent cancellation and no-show probabilities. Our solution approach allows treating each patient as his or her own class. The approximate policy iteration approach is simulation-based and can accommodate complex system dynamics. Our numerical study shows that the approach is competitive against several computational benchmarks.

J. M. Colmenar, M. Laguna, R. Martín-Santamaría

We tackle a capacitated lot-sizing and scheduling problem (CLSP) with the main objective of minimizing changeover time in the production of metal parts for car seats. Changeovers occur when a machine (or production line) is reconfigured to produce a different product or part, leading to production downtime and loss of efficiency. In this study, we first provide a mixed-integer programming (MIP) formulation of the problem. We test the limits of solving the problem with commercial mathematical programming software. We also propose two approaches to tackle instances found in practice for which the mathematical programming model is not a viable solution method. Both approaches are based on partitioning the entire production of a part into production runs (or work slots). In the first approach, the work slots are assigned to machines and sequenced by a metaheuristic that follows the search principles of the GRASP (greedy randomized adaptive procedure) and VNS (variable neighborhood search) methodologies. In the second approach, we develop a Hexaly Optimizer (formerly known as LocalSolver) model to assign and sequence work slots. The study provides insights into how to minimize changeovers and improve production efficiency in metal parts manufacturing for car seats. The findings of this study have practical implications for the auto-part manufacturing industry, where efficient and cost-effective production is critical to meet the demands of the market.

R. Martín-Santamaría, A. Martínez-Gavara, A.D. López-Sánchez, and M. Laguna

We propose a reference framework to apply the multiparent path relinking (MPR) methodology. MPR is an extension of path relinking (PR) that has been proposed and described but, to the best of our knowledge, it has never been applied. PR is a trajectory-based neighborhood search strategy that explores paths that traverse pairs of solutions. PR has been widely used for search intensification purposes within metaheuristic implementations. To show how MPR can be embedded in more than one setting, our proposal consists of both employing MPR as a post-processing step in a greedy randomized adaptive search procedure (GRASP) and as the combination method in a scatter search (SS). We use the power dominating set problem (PDSP) as our testing platform because its difficulty and structure enable the design and assessment of various strategies. The PDSP seeks to find the minimum placement of measurement devices in an electrical network to monitor the entire system. Our computational experiments are designed to identify the contribution of each element of our proposed MRP implementations.

Lot-sizing and scheduling of parallel production lines to minimize changeovers and deviations from target inventory levels
S. Cavero and M. Laguna

The production scheduling problem that we tackle concerns the manufacturing of car seats. A manufacturing facility uses molds and foam to make the inside of a seat for a variety of car models. Carriers with molds are mounted on a limited number of positions in production lines that have the shape of a racetrack. The problem consists of determining the sequence of carriers to mount in each position of each production line to keep inventory levels as close as possible to desired target values at the end of the planning horizon, while minimizing the total number of changeovers. We formulate the problem as mixed integer program and test the limits of the problem sizes that commercial mathematical programming software (Gurobi) can tackle. We also find heuristic solutions with both commercial software (LocalSolver) and a metaheuristic procedure.

Parallel scatter search and path relinking for combinatorial optimization
J. Sánchez-Oro and M. Laguna

The literature includes several proposals to take advantage of parallel processing in the context of scatter search and path relinking. A popular process to arrive at the best-performing configuration of a scatter search has been to design several versions of each of the context-specific methods within the implementation. Thus, the task often involves designing several construction procedures to generate diverse solutions, several combination methods, and several local searches. Preliminary testing is then performed to determine which configuration seems the most effective. We explore the development of a parallel computer framework that can use multiple alternatives for the context-specific methods within scatter search and path relinking. This not only eliminates the need for identifying the “best configuration” but also expands the exploration capabilities of the resulting procedure. To test our conjectures, we apply the parallel framework to published serial scatter search procedures for three combinatorial optimization problems: max-cut, bandpass, and profile minimization.

Scatter search for bilevel linear programming problems
H. I. Calvete, C. Galé, J. A. Iranzo, and M. Laguna

Bilevel programming has its origins in the so-called Stackelberg game. Most bilevel programming research has focused on the linear version of the problem. Bilevel programming considers a hierarchical decision-making structure in which lower-level decisions are made by a follower after, and in view, of the decisions made by the leader at the higher level. Even the linear case of bilevel programming results in a strongly NP-hard problem with a nonconvex search space. We propose an adaptation of scatter search and path relinking to tackle bilevel linear programs (BLPs). In our procedure, solutions are represented as sets of basic variables and therefore the task is to search for the best basis. Diversification generation is achieved by a controlled randomization of existing methods that are designed to create feasible BLP solutions. Our improvement method consists of a neighborhood search that moves along the so-called induced region. The search is allowed to go outside the feasible region when connecting reference solutions via a path relinking process. Experimentation includes both scientific testing (to assess the contribution of the search strategies within the procedure) and competitive testing (to establish the merit of our proposal when compared to the state-of-the-art).