Makespan minimization in a job shop with a BPM using simulated annealing
A scheduling problem commonly observed in the metal working industry has been studied in this research effort -- A job shop equipped with one batch processing machine (BPM) and several unit-capacity machines has been considered. Given a set of jobs, their process routes,processing requirements, and...
- Autores:
-
Rojas Santiago, Miguel
Vélez Gallego, Mario César
Damodaran, Purushothaman
Muthuswamy, Shanthi
Rojas Santiago, Miguel
Vélez Gallego, Mario César
Damodaran, Purushothaman
Muthuswamy, Shanthi
- Tipo de recurso:
- Fecha de publicación:
- 2013
- Institución:
- Universidad EAFIT
- Repositorio:
- Repositorio EAFIT
- Idioma:
- eng
- OAI Identifier:
- oai:repository.eafit.edu.co:10784/5038
- Acceso en línea:
- http://hdl.handle.net/10784/5038
- Palabra clave:
- Metal trade
Genetic algorithms
Heuristic programming
Simulation methods
Combinatorial optimization
INDUSTRIA METALÚRGICA
ALGORITMOS GENÉTICOS
PROGRAMACIÓN HEURÍSTICA
MÉTODOS DE SIMULACIÓN
OPTIMIZACIÓN COMBINATORIA
INDUSTRIA METALÚRGICA
ALGORITMOS GENÉTICOS
PROGRAMACIÓN HEURÍSTICA
MÉTODOS DE SIMULACIÓN
OPTIMIZACIÓN COMBINATORIA
Metal trade
Genetic algorithms
Heuristic programming
Simulation methods
Combinatorial optimization
- Rights
- closedAccess
- License
- Acceso cerrado
| Summary: | A scheduling problem commonly observed in the metal working industry has been studied in this research effort -- A job shop equipped with one batch processing machine (BPM) and several unit-capacity machines has been considered. Given a set of jobs, their process routes,processing requirements, and size, the objective is to schedule the jobs such that the makespan is minimized -- The BPM can process a batch of jobs as long as its capacity is not exceeded -- The batch processing time is equal to the longest processing job in the batch -- If no batches were to be formed, the scheduling problem under study reduces to the classicaljob shop problem with makespan objective, which is known to be nondeterministic polynomial time-hard -- A network representation of the problem using disjunctive and conjunctive arcs, and a simulated annealing (SA) algorithm are proposed to solve the problem. The solution quality and run time of SA are compared with CPLEX, a commercial solver used to solve the mathematical formulation and with four dispatching rules -- Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using SA to solve large-scale problems |
|---|