Backtracking and exchange of information: Methods to enhance a beam search algorithm for assembly line scheduling. (English) Zbl 1149.90130
Summary: Beam search (BS) is used as a heuristic to solve various combinatorial optimization problems, ranging from scheduling to assembly line balancing. In this paper, we develop a backtracking and an exchange-of-information (EOI) procedure to enhance the traditional beam search method. The backtracking enables us to return to previous solution states in the search process with the expectation of obtaining better solutions. The EOI is used to transfer information accumulated in a beam to other beams to yield improved solutions.
We developed six different versions of enhanced beam algorithms to solve the mixed-model assembly line scheduling problem. The results of computational experiments indicate that the backtracking and EOI procedures that utilize problem specific information generally improve the solution quality of BS.
We developed six different versions of enhanced beam algorithms to solve the mixed-model assembly line scheduling problem. The results of computational experiments indicate that the backtracking and EOI procedures that utilize problem specific information generally improve the solution quality of BS.
MSC:
| 90C27 | Combinatorial optimization |
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Abdou, S.; Scordilis, M. S., Beam search pruning in speech recognition using a posterior probability-based confidence measure, Speech Communication, 42, 409-428 (2004) |
| [2] | Alexouda, G.; Paparrizos, K., A genetic algorithm approach to the product line design problem using the seller’s return criterion: An extensive comparative computational study, European Journal of Operational Research, 134, 165-178 (2001) · Zbl 0990.90580 |
| [3] | Bautista, J.; Companys, R.; Corominas, A., Heuristics and exact algorithms for solving the Monden problem, European Journal of Operational Research, 88, 101-113 (1996) · Zbl 0913.90159 |
| [4] | Beraldi, P.; Ruszczynski, A., Beam search heuristic to solve stochastic integer problems under probabilistic constraints, European Journal of Operational Research, 167, 35-47 (2005) · Zbl 1074.90031 |
| [5] | Blum, C., Beam-ACO-hybridizing ant colony optimization with beam search: An application to open shop scheduling, Computers & Operations Research, 32, 1565-1591 (2005) · Zbl 1122.90427 |
| [6] | Chang, Y.; Matsuo, H.; Sullivan, R. S., A bottleneck-based beam search for job scheduling in a flexible manufacturing system, International Journal of Production Research, 27, 1949-1961 (1989) |
| [7] | Della Croce, F. D.; T’kindt, V., A recovering beam search algorithm for the one-machine dynamic total completion time scheduling problem, Journal of The Operational Research Society, 53, 1275-1280 (2002) · Zbl 1103.90338 |
| [8] | Della Croce, F. D.; Ghirardi, M.; Tadei, R., Recovering beam search: Enhancing the beam search approach for combinatorial optimization problems, Journal of Heuristics, 10, 89-104 (2004) · Zbl 1061.90093 |
| [9] | Ding, F. Y.; Cheng, L., An effective mixed-model assembly line sequencing heuristic for just-in-time production systems, Journal of Operations Management, 11, 45-50 (1993) |
| [10] | Erel, E.; Sabuncuoglu, I.; Sekerci, H., Stochastic assembly line balancing using beam search, International Journal of Production Research, 43, 1411-1426 (2005) · Zbl 1068.90045 |
| [11] | Esteve, B.; Aubijoux, C.; Chartier, A.; T’kindt, V., A recovering beam search algorithm for the single machine just-in-time scheduling problem, European Journal of Operational Research, 172, 798-813 (2006) · Zbl 1111.90039 |
| [12] | Forshed, J.; Torgrip, R. J.O.; Aberg, K. M.; Karlberg, B.; Lindberg, J.; Jacobsson, S. P., A comparison of methods for alignment of NMR peaks in the context of cluster analysis, Journal of Pharmaceutical and Biomedical Analysis, 38, 824-832 (2005) |
| [13] | Ghirardi, M.; Potts, C. N., Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach, European Journal of Operational Research, 165, 457-467 (2005) · Zbl 1066.90029 |
| [14] | Honda, N., Mohri, S., Ishii, H., 2003. Backtracking beam search applied to multi-objective scheduling problem. In: The Fifth Metaheuristics International Conference, Kyoto, pp. 1-6.; Honda, N., Mohri, S., Ishii, H., 2003. Backtracking beam search applied to multi-objective scheduling problem. In: The Fifth Metaheuristics International Conference, Kyoto, pp. 1-6. |
| [15] | Jin, M.; Wu, S. D., A new heuristic method for mixed model assembly line balancing problem, Computers and Industrial Engineering, 44, 159-169 (2002) |
| [16] | Kim, K. H.; Kim, K. Y., Routing straddle carriers for the loading operation of containers using a beam search algorithm, Computers and Industrial Engineering, 36, 109-136 (1999) |
| [17] | Kim, K. H.; Kang, J. S.; Ryu, R. K., A beam search algorithm for the load sequencing of outbound containers in port container terminals, OR Spectrum, 26, 93-116 (2004) · Zbl 1161.90410 |
| [18] | Lee, G. C.; Woodruff, D. L., Beam search for peak alignment of NMR signals, Analytica Chimica Acta, 513, 413-416 (2004) |
| [19] | Leu, Y.; Huang, P. Y.; Russell, R. S., Using beam search techniques for sequencing mixed-model assembly lines, Annals of Operations Research, 70, 379-397 (1997) · Zbl 0890.90103 |
| [20] | Lim, A.; Rodrigues, B.; Zhang, X., Scheduling sports competitions at multiple venues-Revisited, European Journal of Operational Research, 175, 171-186 (2006) · Zbl 1137.90504 |
| [21] | Lowerre, B.T., 1976. The HARPY speech recognition system, Ph.D. Thesis, Carnegie Mellon University, Pittsburgh, PA.; Lowerre, B.T., 1976. The HARPY speech recognition system, Ph.D. Thesis, Carnegie Mellon University, Pittsburgh, PA. |
| [22] | Matsuda, T., Motoda, H., Yoshida, T., Washio, T., 2002. Mining patterns from structured data by beam-wise graph-based induction. In: Proceedings of the 5th International Conference on Discovery Science Discovery, vol. 2534, pp. 422-429.; Matsuda, T., Motoda, H., Yoshida, T., Washio, T., 2002. Mining patterns from structured data by beam-wise graph-based induction. In: Proceedings of the 5th International Conference on Discovery Science Discovery, vol. 2534, pp. 422-429. · Zbl 1024.68573 |
| [23] | McMullen, P. R.; Tarasewich, P., A beam search heuristic method for mixed-model scheduling with setups, International Journal of Production Economics, 96, 273-283 (2005) |
| [24] | Miltenburg, J.; Sinnamon, G., Algorithms for scheduling multi-level just-in-time production systems, IIE Transactions, 24, 121-130 (1992) |
| [25] | Monden, Y., Toyota Production System (1983), Institute of Industrial Engineers: Institute of Industrial Engineers Norcross, GA, USA |
| [26] | Ortmanns, S.; Ney, H., Look-ahead techniques for fast beam search, Computer Speech and Language, 14, 15-32 (2000) |
| [27] | Ow, S. P.; Morton, T. E., Filtered beam search in scheduling, International Journal of Production Research, 26, 35-62 (1988) |
| [28] | Pacciarelli, D.; Pranzo, M., Production scheduling in a steelmaking-continuous casting plant, Computers and Chemical Engineering, 28, 2823-2835 (2004) |
| [29] | Sabuncuoglu, I.; Karabuk, S., A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems, IIE Transactions, 30, 179-191 (1998) |
| [30] | Sabuncuoglu, I.; Bayiz, M., Job shop scheduling with beam search, European Journal of Operational Research, 118, 390-412 (1999) · Zbl 0940.90037 |
| [31] | Sabuncuoglu, I.; Bayiz, M., Analysis of reactive scheduling problems in a job shop environment, European Journal of Operational Research, 126, 567-586 (2000) · Zbl 0976.90045 |
| [32] | Shahookar, K., Khamisani, W., Mazumder, P., Reddy, S.M., 1993. Genetic beam search for gate matrix layout. In: Proceedings of the 6th International Conference on VLSI Design, pp. 208-213.; Shahookar, K., Khamisani, W., Mazumder, P., Reddy, S.M., 1993. Genetic beam search for gate matrix layout. In: Proceedings of the 6th International Conference on VLSI Design, pp. 208-213. |
| [33] | Shayan, E.; Al-Hakim, L., Beam search for sequencing point operations in flat plate manufacturing, Computers and Industrial Engineering, 42, 309-315 (2002) |
| [34] | Tillmann, C.; Ney, H., Word reordering and a dynamic programming beam search algorithm for statistical machine translation, Computational Linguistics, 29, 97-133 (2003) · Zbl 1234.68433 |
| [35] | Valente, J. M.S.; Alves, R. A.F. S., Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time, Computers and Industrial Engineering, 48, 363-375 (2005) · Zbl 1095.90046 |
| [36] | Wang, J., A fuzzy project scheduling approach to minimize schedule risk for product development, Fuzzy Sets and Systems, 127, 99-116 (2002) · Zbl 0993.90053 |
| [37] | Zeng, X., Martinez, T.R., 2002. Optimization by varied beam search in hopfield networks. In: Proceedings of the IEEE International Joint Conference on Neural Networks, pp. 913-918.; Zeng, X., Martinez, T.R., 2002. Optimization by varied beam search in hopfield networks. In: Proceedings of the IEEE International Joint Conference on Neural Networks, pp. 913-918. |
| [38] | Zhou, R., Hansen, E.A., 2004. Breadth-first heuristic search. In: Proceedings of the 14th International Conference on Automated Planning and Scheduling.; Zhou, R., Hansen, E.A., 2004. Breadth-first heuristic search. In: Proceedings of the 14th International Conference on Automated Planning and Scheduling. · Zbl 1131.68101 |
| [39] | Zhou, B.; Xi, L.; Cao, Y., A beam-search-based algorithm for the tool switching problem on a flexible machine, International Journal of Advanced Manufacturing Technology, 25, 876-882 (2005) |
| [40] | Zhou, X.; Zhong, M., Bicriteria train scheduling for high-speed passenger railroad planning applications, European Journal of Operational Research, 167, 752-771 (2005) · Zbl 1077.90033 |
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.
