Passengers' requirements in relation to the Airport Service Quality is rapidly increasing and forcing companies and airport management to improve the services performances. It is clear that this enhancement can not overlook the implication of competitive issues and economic concerns. In this paper the authors deal with the optimization of the check-in area management in the international airport of Lisbon. The proposed bi-criteria objective function minimizes the operational costs plus the costs measuring the passengers' discomfort in terms of waiting time in line. The quality of the supplied check-in service is measured and mapped into the Levels of Service system standardized by the International Air Transport Association. The type of passengers and their stochastic behavior and preferences are simulated by a discrete event model. The operational costs and the passengers' satisfaction are optimized by an algorithm based on the Surrogate Method, the performance of which are compared to those of a greedy heuristic and of a genetic algorithm.