Thesis:

Solving a highly-constrained bi-objective shift scheduling problem using a specialized NSGA-II

Workforce shift scheduling is a central problem in human resource management, particularly in contexts characterized by multiple operational constraints and individual preferences. The Employee Shift Scheduling Problem (ESSP) exhibits high combinatorial complexity and inherently conflicting objectives, such as meeting coverage requirements while preserving employee satisfaction. Traditional approaches have typically addressed these aspects through single-objective formulations, which limit the explicit analysis of trade-offs between workforce well-being and operational efficiency. This thesis addresses the ESSP from a bi-objective optimization perspective, explicitly separating the minimization of employee dissatisfaction from the minimization of penalties associated with coverage deviations. To this end, a specialized adaptation of the evolutionary algorithm NSGA-II is proposed, specifically designed to operate within a highly constrained search space. The approach incorporates a hybrid representation based on feasible work sequences, allowing a relevant subset of constraints to be handled implicitly and enabling the design of problem-specific genetic operators. The algorithm includes a feasibility-oriented initialization phase and an automatic parameter tuning process using ParamILS. Experimental validation is conducted on ten benchmark instances from the state of the art, with results compared against an exact method based on integer linear programming implemented in AMPL and solved with Gurobi. Performance is evaluated using the hypervolume indicator and Pareto front analysis. The results show that the proposed approach is capable of generating competitive solution sets, particularly for larger instances, and highlight the significant influence of instance structural characteristics on algorithmic performance.

La planificación de turnos laborales es un problema clave en la gestión de recursos humanos, especialmente en contextos con múltiples restricciones operativas y preferencias individuales. El Employee Shift Scheduling Problem (ESSP) presenta una elevada complejidad combinatoria y objetivos conflictivos, como el cumplimiento de la cobertura requerida y la satisfacción de los empleados. Tradicionalmente, estos aspectos han sido abordados mediante formulaciones monoobjetivo, lo que limita el análisis explícito de los compromisos entre bienestar laboral y eficiencia organizacional. En este trabajo se aborda el ESSP desde una perspectiva de optimización biobjetivo, separando la minimización de la insatisfacción de los empleados y la minimización de las penalizaciones por incumplimiento de cobertura. Para ello, se propone una adaptación especializada del algoritmo evolutivo NSGA-II, diseñada para operar en un espacio de búsqueda altamente restringido. La propuesta incorpora una representación híbrida basada en secuencias factibles, que permite manejar implícitamente un subconjunto relevante de restricciones y facilita el diseño de operadores genéticos especializados. El algoritmo incluye una fase de construcción inicial orientada a favorecer la factibilidad y una parametrización automática mediante ParamILS. La validación experimental se realiza sobre diez instancias de referencia del estado del arte, comparando los resultados con un método exacto basado en programación lineal entera (AMPL/Gurobi). La evaluación se lleva a cabo mediante el indicador de hipervolumen y el análisis de frentes de Pareto. Los resultados muestran que el enfoque propuesto genera soluciones competitivas, especialmente en instancias de mayor tamaño, y evidencian que las características estructurales del problema influyen de manera significativa en el desempeño algorítmico