Alternative representations and multirecombined approaches for solving the single-machine common due date problem

Abstract

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.