91�Թ���

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.

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.

Colmenar, J. M., M. Laguna, and R. Martín

Tabu Search is a metaheuristic renowned for its ability to navigate complex solution spaces by iteratively exploring neighborhoods and intelligently diversifying the search process to avoid getting trapped in local optima. We describe the main elements of the tabu search methodology in the context of finding high-quality solutions to the minimum dominating set problem (MDSP). The MDSP is a fundamental combinatorial optimization challenge with applications in various fields, including network design, social network analysis, and bioinformatics.

Uguina, A. R., A. Martínez-Gavara, and M. Laguna

We introduce the 𝑘-Group 𝑝-Dispersion Problem ((𝑘, 𝑝)-GDP) as a new mathematical model that extends the well-studied 𝑝-dispersion problem (𝑝-DP). The proposed model forms 𝑘 teams, each comprising 𝑝 diverse individuals, such that the minimum pairwise diversity within each group is maximized. This problem has practical applications in workforce management, consulting, and interdisciplinary research teams, where diversity is essential for decision-making and creative problem-solving. Given the NP-hard nature of the problem, we develop an advanced solution methodology that integrates heuristic and exact approaches. We formulate the (𝑘, 𝑝)-GDP as an integer programming problem and adapt three linear formulations of the 𝑝-DP. Additionally, we propose a step-by-step formulation inspired by existing exact methods to improve computational efficiency. Furthermore, we introduce a novel matheuristic based on the Biased Greedy Randomized Adaptive Search Procedure (B-GRASP) combined with a mathematical combination method (MCM). Through extensive computational experiments, we evaluate the performance of our proposed methods, analyze the structural properties of the solutions, and compare them to the traditional 𝑝-dispersion problem. Our findings demonstrate the effectiveness of the proposed approach in generating high-quality diverse teams, providing valuable insights for both theoretical research and practical applications.