We study a new multiobjective job scheduling problem 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.
Metaheuristics for a job scheduling problem with smoothing costs relevant for the car industry
AMALDI, EDOARDO
2016-01-01
Abstract
We study a new multiobjective job scheduling problem 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.File | Dimensione | Formato | |
---|---|---|---|
job-scheduling-Networks-16.pdf
Accesso riservato
:
Publisher’s version
Dimensione
717.37 kB
Formato
Adobe PDF
|
717.37 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.