Este documento aborda el problema de programar un conjunto de trabajos en una máquina con capacidad variable en el tiempo, con el objetivo de minimizar la función objetivo de la tardanza total. Este problema surgió en el contexto de programar los tiempos de carga de una flota de vehículos eléctricos y es NP-duro. Trabajos recientes propusieron un algoritmo memético eficiente para resolver el problema, combinando un algoritmo genético y un método de búsqueda local. El procedimiento de búsqueda local se basa en intercambiar trabajos consecutivos en un C-camino, definido como una secuencia de trabajos consecutivos en una programación. Basándose en esto, este documento desarrolla nuevos algoritmos meméticos que se derivan de nuevos procedimientos de búsqueda local también propuestos en este documento. Los métodos de búsqueda local integran varios mecanismos para hacerlos más efectivos, incluyendo una nueva condición para intercambiar pares de trabajos, un enfoque de escalada de colina, un procedimiento que opera en varios C-caminos y un método que intercambia trabajos entre diferentes C-caminos. Como resultado, los nuevos métodos de búsqueda local permiten que los algoritmos meméticos alcancen soluciones de mayor calidad. Los resultados experimentales muestran mejoras significativas sobre enfoques existentes.