Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics

作者：Alvarez Valdes R^*; Tamarit J M; Villa F

来源：Computers & Operations Research, 2015, 54: 1-11.

DOI：10.1016/j.cor.2014.08.020

• Scheduling
• Earliness-tardiness
• Parallel machines
• Hybrid metaheuristics
• Path Relinking
• Scatter Search

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.

• 出版日期2015-2