Retail business staff scheduling under complex labor relations

The staff scheduling problem in the retail business is considered for which a new mathematical model and new solution methods are introduced. The problem is formalized as a set covering type problem. Columns represent feasible weekly working time patterns of one sales clerk. Rows correspond to periods derived from the weekly opening time. For each period the number of required sales clerks is given. Based on the complex labor rules in Germany a graph is constructed in such a way that a path through the graph represents a weekly working time pattern. A feasible weekly working time pattern is generated by solving a restricted minimum cost path problem in the graph. Different approaches are introduced to compute lower and upper bounds. In particular, a new upper bounding method is presented in which dual variables are defined heuristically. The different approaches are compared by a numerical investigation.