A tree search algorithm for the crew scheduling problem |
| |
| Affiliation: | 1. School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China;2. Key Laboratory of Image Processing and Intelligent Control (Huazhong University of Science and Technology), Ministry of Education, China;3. Division of Computer Science and Mathematics, University of Stirling, Stirling FK9 4LA, UK;1. College of Computer, National University of Defense Technology, Changsha 410073, China;2. School of Aeronautics and Astronautics, Sun Yat-Sen University, Guangzhou 510275, China |
| |
| Abstract: | In this paper we consider the crew scheduling program, that is the problem of assigning K crews to N tasks with fixed start and finish times such that each crew does not exceed a limit on the total time it can spend working.A zero-one integer linear programming formulation of the problem is given, which is then relaxed in a lagrangean way to provide a lower bound which is improved by subgradient optimisation. Finally a tree search procedure incorporating this lower bound is presented to solve the problem to optimality.Computational results are given for a number of randomly generated test problems involving between 50 and 500 tasks. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
