The Capacitated Lot Sizing-Problem (CLSP) consists of planning the lot sizes of multiple items over a planning horizon with the objective of minimizing setup and inventory holding costs. In each period that an item is produced a setup cost is incurred. Capacity is limited and homogeneous. Here, the CLSP is extended to include overtime decisions and capacity consuming setups. The objective function consists of minimizing inventory holding and overtime costs. Setups incur costs implicitly via overtime costs, that is, they lead to additional overtime costs when setup times contribute to the use of overtime capacity in a certain period. The resulting problem becomes more complicated than the standard CLSP and requires methods different from the ones proposed for the latter. Consequently, new heuristic approaches are developed to deal with this problem. Among the heuristic approaches are the classical HPP approach and its modifications, an iterative approach omitting binary variables in the model, a Genetic Algorithm approach based on the transportation-like formulation of the single item production planning model with dynamic demand and a Simulated Annealing approach based on shifting family lot sizes among consecutive periods. Computational results demonstrate that the Simulated Annealing approach produces high quality schedules and is computationally most efficient.