Brusco, Michael J.; Jacobs, Larry W. A simulated annealing approach to the cyclic staff-scheduling problem. (English) Zbl 0769.90056 Nav. Res. Logist. 40, No. 1, 69-84 (1993). Summary: This article presents the application of a simulated annealing heuristic to an NP-complete cyclic staff-scheduling problem. The new heuristic is compared to branch-and-bound integer programming algorithms, as well as construction and linear programming-based heuristics. It is designed for use in a continuously operating scheduling environment with the objective of minimizing the number of employees necessary to satisfy forecast demand. The results indicate that the simulated annealing-based method tends to dominate the branch-and-bound algorithms and the other heuristics in terms of solution quality. Moreover, the annealing algorithm exhibited rapid convergence to a low-cost solution. The simulated annealing heuristic is executed in a single program and does not require mathematical programming software. Cited in 23 Documents MSC: 90B70 Theory of organizations, manpower planning in operations research 90B35 Deterministic scheduling theory in operations research 90C10 Integer programming 90-08 Computational methods for problems pertaining to operations research and mathematical programming 90C05 Linear programming Keywords:simulated annealing; NP-complete cyclic staff-scheduling; branch-and- bound PDFBibTeX XMLCite \textit{M. J. Brusco} and \textit{L. W. Jacobs}, Nav. Res. Logist. 40, No. 1, 69--84 (1993; Zbl 0769.90056) Full Text: DOI References: [1] Abramson, Management Science 37 pp 98– (1991) [2] Bartholdi, Operations Research 29 pp 501– (1981) [3] Bartholdi, Operations Research 28 pp 1074– (1980) [4] Bechtold, Decision Sciences 22 pp 683– (1991) [5] Bechtold, Management Science 36 pp 1339– (1990) [6] Bechtold, Decision Sciences 18 pp 89– (1987) [7] Cerny, Journal of Optimization Theory and Applications 45 pp 41– (1985) [8] Cheh, Computers and Operations Research. 18 pp 537– (1991) [9] Dantzig, Operations Research 2 pp 339– (1954) · Zbl 0204.18701 [10] Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991. [11] Easton, Management Science 37 pp 1441– (1991) [12] Glover, ORSA Journal on Computing 1 pp 190– (1989) · Zbl 0753.90054 [13] Glover, ORSA Journal on Computing 2 pp 4– (1990) · Zbl 0771.90084 [14] Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, 1975. [15] Hopfield, Proceedings of the National Academy of Sciences, U.S.A. 79 pp 2554– (1982) [16] Hopfield, Biological Cybernetics 52 pp 141– (1985) [17] Johnson, Operations Research 37 pp 865– (1989) [18] Johnson, Operations Research 39 pp 378– (1991) [19] Keith, AIIE Transactions 11 pp 37– (1979) [20] Kirkpatrick, Science 220 pp 671– (1983) [21] Kuik, European Journal of Operational Research 45 pp 25– (1990) [22] Metropolis, Journal of Chemical Physics 21 pp 1087– (1953) [23] Morris, Management Science 29 pp 942– (1983) [24] SAS/OR User’s Guide, Version 6. SAS Institute Inc., Cary, NC, 1989. [25] The Nag Fortran Library Manual, Mark 14. Numerical Algorithms Group, Ltd., Oxford, U.K., 1991. [26] Vakharia, Naval Research Logistics 37 pp 559– (1990) [27] Vohra, Journal of the Operational Research Society 39 pp 1057– (1988) 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.