Mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications are presented. In these problems, the daily assignments to be performed are given and the duration (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. The problem is decomposed into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Computational results on real life instances associated with an emergency call center are presented. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months.