Knowledge-based system for rostering

摘要

Scheduling problems are commonly found in servicing and manufacturing industries. In order to maximize the utilization of the supporting hardware and machines, machine operators usually are required to work on shift so that machines remain running continuously without stopping. The construction of the shift duty assignment, usually called roster, is a nontrivial task since many factors need to be considered, such as the maximum number of hours an operator can work continuously and the minimum rest time between two consecutive duties. Since the construction of roster requires nontrivial intellectual activities, it is difficult to computerize roster scheduling using conventional data processing techniques. On the other hand, such roster planning process has been performed by the human planner for years, and experience has been collected to perform the planning task efficiently. Knowledge-based approach takes advantage of human expertise and thus is used to automate the roster scheduling activities. We report here a case study on designing and implementing a computer rostering system for a group of airport servicing staffs using knowledge-based approach. Prototyping is used in the development process. Knowledge is represented in two different forms, namely forward chaining rules and constraints. Forward chaining and iterative improvement are used as control strategies in the system. The first prototype was completed in less than a month. During the refinement process, a tool, called SHO, was developed to simplify the modification process. The whole system was completed in approximately 6 months, of which most of the time was spent on knowledge and rules refinement. Initial implementation was developed using Common Lisp on a Sun Workstation. It is then ported to PC Scheme, a Lisp dialect, on an IBM Personal Computer. The system has been used for rostering up to 500 airport servicing staffs for a few years. As most knowledge and rules have been incorporated into the system, the system has been rewritten in C recently so that the knowledge-based system can communicate with other systems in the organization and has a better performance.