In some industries, forecasted minimum demand for personnel varies from season to another, the maximum (non-overtime) workload per employee can differ between periods for which shifts are planned, compensatory personnel is not available, and recruitment requires a long training period for a class of new employees. We discuss how operations research can be used to support cost-efficient scheduling of employees’ vacations for one calendar year. This process is further complicated by several conditions set by collective bargaining and law, the need for unbiased and fair treatment of employees in various aspects, and the goal of acknowledging employees’ wishes on their vacation schedule. We develop a MILP model to solve the above-mentioned problem and discuss how the model will be applied to schedule vacations of some 1000 employees in 26 depots in Finland.