Alternative representations and multirecombined approaches for solving the single-machine common due date problem
Balance between exploitation and exploration is a main factor influencing convergence in an evolutionary algorithm. In order to improve this balance new trends in evolutionary algorithms make use of multi-recombinative approaches, known as multiple-crossovers-on-multiple-parents (MCMP). The use of...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Español |
| Publicado: |
2001
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/23415 |
| Aporte de: |
| Sumario: | Balance between exploitation and exploration is a main factor influencing convergence in an evolutionary algorithm. In order to improve this balance new trends in evolutionary algorithms make use of multi-recombinative approaches, known as multiple-crossovers-on-multiple-parents (MCMP).
The use of a breeding individual (stud) which repeatedly mates individuals that randomly immigrates to a mating pool can further help the balance between exploration and exploitation.
For the single-machine common due date problem an optimal schedule is V-shaped around the due date. To produce V-shaped schedules an appropriate binary representation, associated with a schedule builder, can be used. In this representation each bit indicates if a corresponding job belongs either to the tardy or the non-tardy set. When contrasted with commonly used permutation representations this approach reduces the searching space from n! to 2n.
This paper compares three different implementations and shows their performance on a set of instances for the single machine scheduling problem with a common due date. Two of these approaches are based on a binary representation to form V-shaped schedules while the other is based on permutations. All these approaches apply different multirecombined methods. Details on implementation and results are discussed. |
|---|