×

Fast local search and guided local search and their application to British Telecom’s workforce scheduling problem. (English) Zbl 0882.90102

Summary: This paper reports a fast local search (FLS) algorithm which helps to improve the efficiency of hill climbing and a guided local search (GLS) algorithm which was developed to help local search to escape local optima and distribute search effort. To illustrate how these algorithms work, this paper describes their application to British Telecom’s workforce scheduling problem, which is a hard real life problem. The effectiveness of FLS and GLS are demonstrated by the fact that they both outperform all the methods applied to this problem so far, which include simulated annealing, genetic algorithms and constraint logic programming.

MSC:

90C10 Integer programming
90B70 Theory of organizations, manpower planning in operations research
90C90 Applications of mathematical programming
90B90 Case-oriented studies in operations research

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E.; Korst, J., Simulated Annealing and Boltzmann Machines (1989), Wiley: Wiley New York · Zbl 0674.90059
[2] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Data Structures and Algorithms (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0307.68053
[3] Azarmi, N.; Abdul-Hameed, W., Workforce scheduling with constraint logic programming, British Telecom Technol. J., 13, 1, 81-94 (1995)
[4] Baker, S., Applying simulated annealing to the workforce management problem, (ISR Technical Report (1993), British Telecom Laboratories, Martlesham Heath: British Telecom Laboratories, Martlesham Heath Ipswich)
[5] Bentley, J. J., Fast algorithms for geometric traveling salesman problems, ORSA J. Comput., 4, 387-411 (1992) · Zbl 0758.90071
[6] Davenport, A.; Tsang, E. P.K.; Wang, C. J.; Zhu, K., GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement, (Proc. 12th National Conf. for Artificial Intelligence (AAAI) (1994)), 325-330
[7] (Davis, L., Genetic Algorithms and Simulated Annealing. Genetic Algorithms and Simulated Annealing, Research Notes in AI (1987), Pitman: Pitman London), Morgan Kaufmann, Los Altos, CA · Zbl 0684.68013
[8] (Davis, L., Handbook of Genetic Algorithms (1991), Van Nostrand Reinhold: Van Nostrand Reinhold New York)
[9] Eiben, A. E.; Raua, P-E.; Ruttkay, Zs., Solving constraint satisfaction problems using genetic algorithms, (Proc., 1st IEEE Conference on Evolutionary Computing (1994)), 543-547
[10] Glover, F., Tabu search Part I, ORSA J. Comput., 1, 109-206 (1989) · Zbl 0753.90054
[11] Glover, F., Tabu search Part II, ORSA J. Comput., 2, 4-32 (1990) · Zbl 0771.90084
[12] Glover, F., Tabu search: improved solution alternatives for real world problems, (Birge; Murty, Mathematical Programming: State of the Art (1994)), 64-92
[13] Glover, F.; Laguna, M., Tabu search, (Reeves, C., Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwell Scientific Publishing: Blackwell Scientific Publishing Oxford), 71-141
[14] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[15] Hall, P. A.V., Branch and bound and beyond, (Proc. Internat. Joint Conf. on AI (1971)), 641-650
[16] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI
[17] Koopman, B. O., The theory of search, part III, the optimum distribution of searching effort, Oper. Res., 5, 613-626 (1957) · Zbl 1414.90176
[18] Lawler, E. W.; Wood, D. E., Branch-and-bound methods: a survey, Oper. Res., 14, 699-719 (1966) · Zbl 0143.42501
[19] Lever, J.; Wallace, M.; Richards, B., Constraint logic programming for scheduling and planning, British Telecom Technol. J., 13, 1, 73-80 (1995)
[20] Muller, C.; Magill, E. H.; Smith, D. G., Distributed genetic algorithms for resource allocation, (Technical Report (1993), Strathclyde University: Strathclyde University Glasgow)
[21] Otten, R. H.J. M.; van Ginneken, L. P.P. P., The Annealing Algorithm (1989), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht
[22] Reingold, E. M.; Nievergelt, J.; Deo, N., Combinatorial Algorithms: Theory and Practice (1977), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0367.68032
[23] Stone, L. D., The process of search planning: current approaches and continuing problems, Oper. Res., 31, 207-233 (1983)
[24] Tsang, E. P.K., Scheduling techniques — a comparative study, British Telecom Technol. J., 13, 1, 16-28 (1995)
[25] van Hentenryck, P., Constraint Satisfaction in Logic Programming (1989), MIT Press: MIT Press Cambridge, MA
[26] Voudouris, C.; Tsang, E. P.K., Guided local search, (Technical Report CSM-247 (August, 1995), Department of Computer Science, University of Essex) · Zbl 1102.90385
[27] Voudouris, C.; Tsang, E. P.K., Function optimization using guided local search, (Technical Report CSM-249 (August, 1995), Department of Computer Science, University of Essex: Department of Computer Science, University of Essex Colchester, UK)
[28] Voudouris, C.; Tsang, E. P.K., Partial constraint satisfaction problems and guided local search, (Proc. Practical Application of Constraint Technology (PACT’96). Proc. Practical Application of Constraint Technology (PACT’96), London (April, 1996))
[29] Wang, C. J.; Tsang, E. P.K., Solving constraint satisfaction problems using neural-networks, (Proc. IEE 2nd Internat. Conf. on Artificial Neural Networks (1991)), 295-299
[30] Warwick, T.; Tsang, E. P.K., Using a genetic algorithm to tackle the processors configuration problem, (Symp. on Applied Computing (1994)), 217-221
[31] Warwick, T.; Tsang, E. P.K., Tackling car sequencing problems using a generic genetic algorithm, Evolutionary Computation, 3, 3, 267-298 (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.