A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blocking (Q2627304)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blocking |
scientific article |
Statements
A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blocking (English)
0 references
31 May 2017
0 references
Summary: In this paper, we study the job shop scheduling problem with blocking where the objective is to minimise the maximum completion time (i.e. makespan). To solve this non-polynomial-hard problem, we propose three algorithms. First, we propose a combination of a branch and bound algorithm with alternative graphs. We investigate the performance of this proposal to get an optimal solution in a reasonable time. Next, we develop two methods based on genetic algorithms (GAs): sequential and parallel GAs. In the former, we propose two different ways to encode the individuals: binary code using alternative arcs and priority rules code. In the latter, we propose a parallelisation of the GA, where the master computer is dedicated to the steps of selection, crossover and mutation, and the other computers (slaves) are concerned with the computation of the individuals fitness. At the end of this paper, we discuss the different results.
0 references
job shop scheduling
0 references
blocking constraints
0 references
alternative graphs
0 references
B\&B
0 references
branch and bound
0 references
parallel genetic algorithms
0 references
operational research
0 references