On a pattern sequencing problem to minimize the maximum number of open stacks. (English) Zbl 0917.90205
Summary: Consider a wood cutting setting where different panels have to be cut from large boards. Each cut panel size is put into a stack which remains opened until the last panel of that size is cut. The problem considered here deals with the sequencing of the patterns in order to minimize the maximum number of open stacks during the production run. A branch-and-bound method for solving this problem is presented which uses a greedy type scheme to select the next node to branch.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
pattern sequencing; tool switches; flexible manufacturing systems; wood cutting; branch-and-boundReferences:
| [1] | Dyckhoff, H.; Finke, U., Cutting and packing in production and distribution: typology and bibliography (1992), Springer Verlag: Springer Verlag Heidelberg |
| [2] | Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E., Complexity results for bandwidth minimization, SIAM Journal of Applied Mathematics, 34/3, 477-495 (1978) · Zbl 0385.05048 |
| [3] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [4] | Harris, R., An industrial application of integer programming, (MSc. Thesis in Industrial Programming Technology (1987), University of Sheffield: University of Sheffield Sheffield) |
| [5] | Lins, S., Traversing trees and scheduling tasks for duplex corrugator machines, Pesquisa operacional, 9/1, 40-54 (1989) |
| [6] | Madsen, O. B.G., An application of travelling salesman routines to solve pattern allocation problems in the glass industry, Journal of the Operational Research Society, 39/3, 249-256 (1988) · Zbl 0638.90047 |
| [7] | Tang, C. S.; Denardo, E. V., Models arising from a flexible manufacturing machine, Part I: minimization of the number of tool switches, Operations Research, 36, 767-777 (1988) · Zbl 0665.90044 |
| [8] | Vasco, F. J.; Wolf, F. E.; Pflugrad, J. A., An efficient heuristic for planning mother plate requirements at Bethlehem steel, Interfaces, 21/2, 1-7 (1991) |
| [9] | Yuen, B. J., Heuristics for sequencing cutting patterns, European Journal of Operational Research, 55/2, 183-190 (1991) · Zbl 0729.90997 |
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.
