Note on an improved branch-and-bound algorithm to solve n/m/P/Fmax problems
Tóm tắt
The LOMNICKI algorithm for n/m/P/Fmax flow-shop problems is unsuitable for large values ofn andm because of the time and size of storage required to attain an optimal solution. The form of presentation of the problem to the algorithm can influence its performance. The algorithm performance can be improved applying the algorithm to the problem and to its inverse at the same time, sharing both applications the best value and the best bound found. Further exploitation of proprieties of the inverse problem are useful also for solve hard instances of the problem.
Tài liệu tham khảo
Brown, A.P.G. & Lomnicki, Z.A. (1966), Some applications of the “branch-and-bound” algorithm to the machine scheduling problem,Operational Research Quarterly,17, n. 4, pp. 173–186.
Carulla, E. & O. Ibañez (1993),Comparació de diverses heuristiques per la resolució del problema de flow-shop, PFC, ETSEIB-UPC.
Companys, R. (1993), Algorithmo de Lomnicki pendular, inNotas sobre el problema del taller mecánico, pp. 51–58, D.I.T. 3/12, ETSEIB-UPC.
Dannenbring, D.G. (1977) An evaluation of flow-shop sequencing heuristics,Management Science,23, n. 6, pp. 1174–1182.
Lomnicki, Z.A. (1965), A branch and bound algorithm for the exact solution of three machines scheduling problems,Operational Research Quarterly,16, n. 4, pp. 89–100.
McMahon, G.B. & Burton, P.G. (1967), Flow-shop scheduling with the branch-and-bound method,Operations Research,15, n. 3, pp. 473–481.
Nabeshima, I. (1967), On the bound of makespans and its application to m machine scheduling problemJournal of Operations Research Society of Japan,9, pp. 98–136.
Palmer, D.S. (1965), Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time,Operational Research Quarterly,16, n. 4, pp. 101–107.
Potts, C.N. (1980), An Adaptive Branching Rule For The Permutation Flow-Shop Problem,European Journal Of Operational Research,5, n. 1, pp. 19–25.
Szwarc, W. (1971), Elimination Method in the mxn Sequencing Problem,Naval Research Logistic Quarterly,18, pp. 295–305.
Vivo, R. (1994),Estudio e Implementación del Algoritmo Lomnicki Pendular, PFC, ETSEIB-UPC.