Algorithm For Call Centers Staff Scheduling Through Multi-Stage Optimization And The Framework Design

Call center rostering problem is a kind of staff scheduling problem, belong to the domain of Operational Research. When the call center produces the roster, it needs to take all the constraint from every aspect into account. While the cost is controlled to be the lowest, the call center tries to get the highest benefit. As the sharply development of the industry of call center, and the refinement of the category of the skills, the constraints are being more and more complicated, and the difficulty of the solving problem is increasing sharply. The traditional Operational Research method consumes large amount computational recourses, but it always could not get any ideal result. In the recent years, kinds of heuristic algorithms in the AI domain are rising up, the solving system with AI algorithms drives the solving procedure fast and effective, efficient rostering software made the call center industry get the huge fortune.The article firstly introduces detailedly every kinds of concept of the rostering problem, through the modeling and the discussing the constraint, it analyzed the problem deeply, mading the reader recognizes the problem correctly and explicitly. At the end of the first chapter, it briefly describe the research situation of the call center rosering problem, introduces a few kinds of effective solving idea and their principle, and introduces and discusses detailedly a classical algorithm of the Blue Pumpkin Director Software.On the base of the work, the article classifies the constraints of the problem, ranking the categories according the constraint strength, analyses the intensity among the kinds of constraints from the aspect of the business logic, and designs a multi-stage optimization method. According to the business logic, we divided the problem into two sub-problems, the shifts creating problem and the shift assignment problem. The algorithm firstly creates sets of shifts for every workday, and then according to the request from the practice business condition, assigns the shift to the class of agents for everyday. The algorithm divides the constraints into the sub-problems, trying best to make the intensity among the constraints from the different sub– problems weakest, alleviating the side effect of the problem decomposition. Thus, we can prune the search space effectively.We would like to call the algorithm as a framework. The article only decomposes the problem in terms of the intensity among the constraints. By the decomposition, the framework designates the solving procedures by the sequence of the constraints. There is a library of algorithms for the different stages and the different conditions of the solving, for example, backtrack search, GA etc. usually could speed up the progress.In lots of literatures, there is a kind of intuitionistic description of the solving procedures as sliding the beginning and the length of the shifts on the time axis, madding the amount of the agents on the every span be close to the demand. Because the traditional un-decomposed model takes a lot of constraints onto a single entity, it can not abstract the sliding concept. In the new model, we divide the assignment of the shifts to the class from the creating the set of shifts, we can solely consider the shifts. The article defines the definition of the shift-chain, and builds the sliding shifts model by the fixing of the shift-chain.On the base of the deep analyzing of the problem, the article sets down some simple and effective search strategy. In lots of algorithms, it usually updates the objective function by the iterative computation. Some soft constraints would consume huge amount of time, however, all the constraints can not be satisfied, and it is no sense to the quantity of the schedule. We design a policy which deals the set of soft constraints by one time, it can progresses almost without the iteration, saving a lot of time, no effecting to the roster.In the shift assignment problem, the algorithm defines the cycle shift rules as the one of the weakest constraints as the agents desire constraints. As the result, we design the dynamic cycle shift rules.The third chapter introduces the framework design and the implement of the roster algorithm software. With the algorithm, it mainly references the architecture, business demand, technique support, object design, and the deployment of the database, talking the design idea of the software package.The mobile objects, the data and the methods are sealed into the entity objects according to the business logic. It avoid the confusedly distributing of the same entity on the different physical level, it is also convenient for the development and the maintenance of the coding. With the concept of data portal and the support of the reflection, the business logic of the whole framework is abstracted from the actual communication and the physical deployment, and the mobile object could transport among the levels freely. By the inheritance the business object base class of the CSLA.NET framework, the programmers only need to code the necessary attributes and the method, reducing the workload of the software development. In the deployment of the database, we display the policy that using the SQL sentences instead of the programming, in this way, it can not only decrease the workload, but also increase the efficiency and the stability.In the test chapter, it provides the speed the multi-stages optimization algorithm and the quantity of the schedule. It manifests that the algorithm can finish the computation in a very short time. In the aspect of the comparing the quantity, it compute the matchness of the spans that cover the continuous workday, and their average and variance, they can show the roster's match grade to the demand. It uses the single day's shifts'lengths and their average and variance to show the violation of the constraints of the shift length for single day, and the situation of the shifts for the single day. The values, their average and variance of the hours of continuous days can manifest the justice of the schedule and the violation of the constraints of the total hours for the continuous days. Compared with the traditional procedures, which define the service goal constraints stronger than the length of the shift constraints, the new procedure's schedule has a good matchness and the situation of the violation of the length of shift constraint out of the scope that we can not accept hardly appear.