Scientific article
English

Metaheuristics for a job scheduling problem with smoothing costs relevant for the car industry

Published in

Networks, vol. 67, no. 3, p. 246-261

Publication date

2016

Abstract

on nonidentical machines with applications in the car industry, inspired by the problem proposed by the car manufacturer Renault in the ROADEF 2005 Challenge. Makespan, smoothing costs and setup costs are minimized following a lexicographic order, where smoothing costs are used to balance resource utilization. We first describe a mixed integer linear programming (MILP) formulation and a network interpretation as a variant of the well-known vehicle routing problem. We then propose and compare several solution methods, ranging from greedy procedures to a tabu search and an adaptive memory algorithm. For small instances (with up to 40 jobs) whose MILP formulation can be solved to optimality, tabu search provides remarkably good solutions. The adaptive memory algorithm, using tabu search as an intensification procedure, turns out to yield the best results for large instances.

Keywords

  • Job scheduling
  • Smoothing cost
  • Unrelated machine
  • Metaheuristic

UNIGE affiliation entities

Citation (ISO format)

RESPEN, Jean, ZUFFEREY, Nicolas, AMALDI, Edoardo. Metaheuristics for a job scheduling problem with smoothing costs relevant for the car industry. In: Networks, 2016, vol. 67, n° 3, p. 246–261. doi: 10.1002/net.21656

Main files (1)

Article (Accepted version)

Identifiers

Journal ISSN

0028-3045
537views
1downloads

Technical informations

Creation

11/01/2017 18:00:00

First validation

11/01/2017 18:00:00

Update

15/03/2023 01:17:30

Status update

15/03/2023 01:17:30

Last indexation

31/10/2024 05:53:30
All rights reserved by Archive ouverte UNIGE and the University of Geneva
OpenAIRE Indexed & Validated