This research presents a Simulated Annealing based technique to address the assembly line balancing problem for multiple objective problems when paralleling of workstations is permitted. The Simulated Annealing methodology is used for 23 line balancing strategies across seven problems. The resulting performance of each solution was studied through a simulation experiment. Many of the problems consisted of multiple products, which were sequenced in a mixed model fashion, task times were assumed to be stochastic, and parallel workstations were permitted. Two primary performance objectives were of most interest: total cost (labour and equipment) per part, and the degree to which the desired cycle time was achieved. Other traditional line balancing and production performance measures were also collected. This paper demonstrates how Simulated Annealing can be used to obtain line balancing solutions when one or more objectives are important. The experimental results showed that Simulated Annealing approaches yielded significantly better solutions on cycle time performance but average solutions on cost performance. When cycle time performance and total unit cost are weighted equally, performance rankings showed that Simulated Annealing approaches still showed better mean performance than the other approaches.