One-Machine Scheduling with Time-Dependent Capacity via Efficient Memetic Algorithms

Raúl Mencía and Carlos Mencía
Additional contact information
Raúl Mencía: Department of Computer Science, University of Oviedo, 33204 Gijón, Spain
Carlos Mencía: Department of Computer Science, University of Oviedo, 33204 Gijón, Spain

Mathematics, 2021, vol. 9, issue 23, 1-24

Abstract: This paper addresses the problem of scheduling a set of jobs on a machine with time-varying capacity, with the goal of minimizing the total tardiness objective function. This problem arose in the context scheduling the charging times of a fleet of electric vehicles and it is NP-hard. Recent work proposed an efficient memetic algorithm for solving the problem, combining a genetic algorithm and a local search method. The local search procedure is based on swapping consecutive jobs on a C-path, defined as a sequence of consecutive jobs in a schedule. Building on it, this paper develops new memetic algorithms that stem from new local search procedures also proposed in this paper. The local search methods integrate several mechanisms to make them more effective, including a new condition for swapping pairs of jobs, a hill climbing approach, a procedure that operates on several C-paths and a method that interchanges jobs between different C-paths. As a result, the new local search methods enable the memetic algorithms to reach higher-quality solutions. Experimental results show significant improvements over existing approaches.

Keywords: one-machine scheduling; time-varying capacity; memetic algorithms; local search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/23/3030/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/23/3030/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:23:p:3030-:d:688474

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().