Simulated annealing is one the most popular methods that provides a means for optimization of problems with both continuous and discrete variables. The method is basically a Monte-Carlo random search technique in which movement from a local extremum is heuristically possible. In this paper, an approach to the design of laminates based on a modified discrete-variables parallel simulated annealing method is presented. The eight effective elastic moduli and the weight of the laminate are used to develop a cost function that its minimization gives a proper lay-up to be compatible with the required elastic effective moduli and a minimum weight. A parallel simulated annealing procedure in conjunction with a novel adaptive cooling schedule is introduced to speed up the algorithm. Studies show that the introduced modifications are also statistically effective in increasing the solution quality.