6533b850fe1ef96bd12a85c5

RESEARCH PRODUCT

Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics

Fulgencia VillaJosé Manuel TamaritRamón Alvarez-valdés

subject

Parallel machinesMathematical optimizationGeneral Computer ScienceSchedulingTardinessESTADISTICA E INVESTIGACION OPERATIVAManagement Science and Operations ResearchScheduling (computing)Path RelinkingDue dateModeling and SimulationHybrid metaheuristicsScatter SearchMetaheuristicEarliness-tardinessMathematics

description

We consider the problem of scheduling a set of jobs on a set of identical parallel machines where the objective is to minimize the total weighted earliness and tardiness penalties with respect to a common due date. We propose a hybrid heuristic algorithm for constructing good solutions, combining priority rules for assigning jobs to machines and a local search with exact procedures for solving the one-machine subproblems. These solutions are then used in two metaheuristic frameworks, Path Relinking and Scatter Search, to obtain high quality solutions for the problem. The algorithms are tested on a large number of test instances to assess the efficiency of the proposed strategies. The results show that our algorithms consistently outperform the best reported results for this problem.

yearjournalcountryeditionlanguage
2015-02-01
10.1016/j.cor.2014.08.020https://doi.org/10.1016/j.cor.2014.08.020