This paper attempts to formalise, solve and optimise (S/O) the Assembly Sequence Planning Problem (ASPP), a large scale, highly constrained combinatorial problem. Due to the complexity of the subject and the number of related matters to be considered/adapted/solved prior to S/O the ASPP, the paper is split in two, self-contained, parts: Part I—Automatic Generation of Feasible Assembly Sequences and Part II—optimisation of assembly sequences using Genetic Algorithms. The first part deals with formalising the ASPP—modelling and representation issues—and generating feasible assembly sequences (solving the ASPP). The second part is concerned with the optimisation of the ASPP and will present in detail the Genetic Algorithm designed to optimise it, the genetic operators that compose the algorithm and the definition of the fitness function (optimisation function). The ASPP is considered here as a full-scale, unabridged problem.