Abstract
We model and solve the problem of sequencing a set of jobs with specified processing times and tool requirements on a set of identical parallel machines. Decisions concern the assignment of jobs to machines, their sequencing, and the allocation of tools on each machine. The objective function minimizes the makespan. We propose two mathematical formulations of the problem and an adaptive large neighborhood search metaheuristic in which the destroy and repair operators exploit the structures of two well-known and related combinatorial optimization problems, namely the parallel machine scheduling problem and the job sequencing and tool switching problem on a single machine. Computational experiments conducted on two data sets of 1440 instances show that our algorithm produces excellent results and outperforms existing heuristics.
| Original language | English |
|---|---|
| Pages (from-to) | 834-844 |
| Number of pages | 11 |
| Journal | European Journal of Operational Research |
| Volume | 257 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 16 Mar 2017 |
Funding
Thanks are due to two anonymous referees for their valuable comments. This work was partially supported by the FAPESP (São Paulo Research Foundation), by the Capes-Brazil (Coordenação de Aperfeiçoamento de Pessoal de NíÃvel Superior), by the Canadian Natural Science and Engineering Research Council under grants 2014–04959 and 2015–06189 and by the CNPq -Brazil (National Council for Scientific and Technological Development). This support is gratefully acknowledged. We also thank CIRRELT and Calcul Québec for providing the computing facilities used for our experiments.
Keywords
- Adaptive large neighborhood search
- Flexible manufacturing systems
- Parallel machines
- Sequence-dependent setup times
- Tooling constraints
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research
- Information Systems and Management