This paper proposes and evaluates fourteen heuristic methods to solve the Alternative Subgraphs Assembly Line Balancing Problem, in which assembly variants (subgraphs) are allowed for different parts of an assembly process. To solve this problem efficiently, both subgraphs selection and task assignment have to be carried out simultaneously. All proposed methods aim at minimizing the number of workstations and use random choice to select the subgraphs and different decision rules to select the tasks to be assigned. The performance of these methods is evaluated and compared by means of a computational experiment based on medium and large scale benchmark problems.