Sufficient Working Subsets for the Tour Scheduling Problem
提出一种基于列生成的工作子集启发式方法，用于服务员工排班问题，实验表明其目标值与使用全部可行班次的模型无差异，且优于其他工作子集方法。
Mathematical programs to schedule service employees at minimum cost represent each feasible schedule, or tour, with an integer variable. In some service organizations, policies governing employee scheduling practices may permit millions of different tours. A common heuristic strategy is to reformulate the problem from a small working subset of the feasible tours. Solution quality depends on the number and types of schedules included in the model. This paper describes a working subset heuristic based on column generation. The method is general and can accommodate a mix of full- and part-time employees. Experiments revealed its formulations had objective values indistinguishable from those of models using all feasible tours, and significantly lower than those generated by alternative working subset procedures.