Achieving efficient and optimized call center scheduling is a critical issue to corporate customer services when considering limited resources and complex constraints. This study combines constraint-based reasoning (CDR) mechanisms and particle swarm optimization (PSO) (CBPSO) to solve timetables scheduling problems for customer service department. When PSO searches for solution space, CBR mechanism can be used to reduce invalid solution space of particle search, and to improve solving efficiency. The experimental results showed that CBPSO is able to overcome the efficiency and flexibly concern under constraints in developing work-force timetables. The produced scheduling timetables can also address the labor cost minimization and fairness maximization.