We present an algorithm for use in an interactive music system that automatically generates music playlists that fit the music preferences given by a user. To this end, we introduce a formal model, define the problem of automatic playlist generation (APG) and indicate its NP-hardness. We use a local search (LS) procedure based on simulated annealing (SA) to solve the APG problem. In order to employ this LS procedure, we introduce an optimization variant of the APG problem, which includes the definition of penalty functions and a neighborhood structure. To improve upon the performance of the standard SA algorithm, we incorporated three heuristics referred to as song domain reduction, partial constraint voting, and two-level neighborhood structure. In tests, LS performed better than a constraint satisfaction (CS) solution in terms of run time, scalability and playlist quality.