UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A method of evaluating bucking and sawing strategies for sawlogs McPhalen, James Charles 1978

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1978_A6 M26.pdf [ 4.07MB ]
Metadata
JSON: 831-1.0075298.json
JSON-LD: 831-1.0075298-ld.json
RDF/XML (Pretty): 831-1.0075298-rdf.xml
RDF/JSON: 831-1.0075298-rdf.json
Turtle: 831-1.0075298-turtle.txt
N-Triples: 831-1.0075298-rdf-ntriples.txt
Original Record: 831-1.0075298-source.json
Full Text
831-1.0075298-fulltext.txt
Citation
831-1.0075298.ris

Full Text

A METHOD OF E V A L U A T I N G BUCKING AND SAWING S T R A T E G I E S FOP SAWLOGS by J A M E S CHARLES MCPHALEN B . S . F . , U n i v e r s i t y o f B r i t i s h C o l u m b i a , 1970 A T H E S I S SUBMITED I N P A R T I A L F U L F I L L M E N T OF T H E REQUIREMENTS FOR THE DEGREE OF MASTER OF FORESTRY in the F A C U L T Y CF GRADUATE S T U D I E S D e p a r t o e n t o f F o r e s t r y We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d THE U N I V E R S I T Y CF B R I T I S H COLUMEIA S e p t e m b e r , 1978 © JAMES CHARLES B C P H A L E N , 1978 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f< an advanced degree at the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e tha the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r ag ree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . It i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f F o r e s t r y  The U n i v e r s i t y o f B r i t i s h Co lumbia 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 Date O c t o b e r 10, 1978 i i A B S T R A C T I n t h e l a s t few y e a r s t h e s a w m i l l i n g i n d u s t r y has f a c e d t h e e c o n o m i c p r e s s u r e o f i n c r e a s i n g raw m a t e r i a l c o s t s , i n c r e a s i i . q c c n v e r s i o n c o s t s a n d l i m i t e d p r o d u c t v a l u e d u e t o c o m p e t i t i o n f r o m o t h e r p r o d u c t s , o n e r e s u l t o f t h i s p r e s s u r e h a s b e e n t h e d e v e l o p m e n t o f p r o c e s s c o n t r o l s y s t e m s w h i c h a u t o m a t e many o f t h e c u t t i n g d e c i s i o n s r e q u i r e d t o c o n v e r t t r e e - l e n q t h l o q s i n t o m a r k e t a b l e p r o d u c t s . R e g a r d l e s s o f w h e t h e r s a w s a r e p o s i t i o n e d a u t o m a t i c a l l y o r m a n u a l l y , a s e t o f c u t t i n g i n s t r u c t i o n s i s e s s e n t i a l . T h e s e i n s t r u c t i o n s s h o u l d , f o r t h e a v a i l a b l e l o g s u p p l y , p r o v i d e t h e m o s t e c o n o m i c a l y i e l d c o n s i s t e n t w i t h m a r k e t d e m a n d s a n d m i l l c o n s t r a i n t s . Two c r i t i c a l d e c i s i o n s a r e made i n c o n v e r t i n g l o q s i n t o l u m b e r . T h e b u c k i n g d e c i s i o n c o n s t r a i n s t h e l u m b e r l e n g t h a n d h e n c e may l i m i t t h e v a l u e o f t h e l u m b e r . T h e s a w i n g d e c i s i o n d e t e r m i n e s t h e l u m b e r p r o d u c t s w h i c h c a n b e sawn f r o m t h e r e s u l t i n g s h o r t l o g s . T h e two d e c i s i o n s c a n n o t b e a n a l y z e d i n i s o l a t i o n . I n o r d e r t o d e t e r m i n e t h e b u c k i n g s t r a t e g y w h i c h y i e l d s t h e mix o f s h o r t l o g s w h i c h w i l l p r o d u c e t h e maximum l u m b e r v a l u e i t i s n e c e s s a r y t o kn'ow t h e s a w i n g p a t t e r n w h i c h w i l l b e u s e d t o c o n v e r t t h e l o g s i n t o l u m b e r . S i m i l a r l y , g i v e n a l i m i t e d l o g s u p p l y o f f i x e d c h a r a c t e r i s t i c s , l i m i t e d s a w m i l l c a p a c i t y a n d r e s t r i c t i o n s on m a r k e t demand f o r l u m b e r p r o d u c t s , t h e o p t i m u m s a w i n g s t r a t e g y c a n n o t b e d e t e r m i n e d w i t h o u t i n f o r m a t i o n o n t h e p o p u l a t i o n o f s h o r t l o q s w h i c h w i l l d e v e l o p f r c m t h e b u c k i n g d e c i s i o n . F o r m u l a t i n g t h e p r o b l e r c o f d e t e r m i n g o p t i m u m b u c k i n q - s a v i n q d e c i s i o n s f o r a l i m i t e d l o g s u p p l y and l i m i t e d s a w m i l l c a p a c i t y a s a l i n e a r p r o g r a m m i n g m o d e l i s a t t r a c t i v e b u t t h e l a r g e number o f a l t e r n a t i v e c u t t i n g d e c i s i o n s make s u c h a f o r m u l a t i o n i n t r a c t a b l e . The p r o b l e m o f d e t e r m i n q o p t i m a l b u c k i n g and s a v i n g s t r a t e g i e s f o r a s i n g l e l o g c a n be m o d e l l e d a s a d y n a m i c p r o g r a m m i n g r e c u r s i o n . However, t h e d y n a m i c p r o g r a m m i n g a p p r o a c h c a n n o t e f f i c i e n t l y h a n d l e t h e l a r g e number o f c o n s t r a i n t s i n h e r e n t i n f o r m u l a t i n g an op t i m u m b u c k i n g - s a w i n g s t r a t e q y f o r a g i v e n p o p u l a t i o n c f t r e e - l e n g t h l o g s . I t was shown t h a t t h e l i n e a r and d y n a m i c p r o q r a m m i n q m o d e l s c o u l d be c o m b i n e d u s i n g D a n t z i g - w o l f e d e c o m p o s i t i o n . The l i n e a r m o d e l d e t e r m i n e s t h e c o m b i n a t i o n o f c u t t i n g s t r a t e g i e s w h i c h o p t i m i z e an o b j e c t i v e f u n c t i o n s u b j e c t t o c o n s t r a i n t s . The d y n a m i c p r o g r a m m i n g m o d e l s u p p l i e s t h e l i n e a r m o d e l w i t h new a c t i v i t i e s a s r e g u i r e d , , T h e d e c o m p o s i t i o n a p p r o a c h i s a t t r a c t i v e b e c a u s e i t a v o i d s t h e n e c e s s i t y o f w o r k i n g w i t h a l l p o s s i b l e a c t i v i t i e s i n t h e l i n e a r p r o g r a m m e . T h e L . P . c a l c u l a t e s w i t h t h e b a s i s i n v e r s e a n d t h e d y n a m i c p r o g r a m m i n g s u b - p r o b l e m g e n e r a t e s new b u c k i n g - s a w i n g a c t i v i t i e s a s r e g u i r e d b y t h e L . P . T h e e f f i c i e n c y o f t h e t e c h n i g u e was d e m o n s t r a t e d by d e t e r m i n g o p t i m a l b u c k i n g a n d s a w i n g s t r a t e g i e s f o r a p o p u l a t i o n o f 967 l o n g l o g s . i v T A B L E OF CONTENTS AEST E ACT . . . i i T a b l e O f C o n t e n t s i v L i s t O f F i g u r e s . . . v i L i s t C f T a b l e s , v i i ACKNOWLEDGEMENTS v i i i 1. I n t r o d u c t i o n • 1 1.1 T r e e L e n g t h L o g g i n g 2 1.2 L e g M e r c h a n d i s e r s 2 1.3 I m p r o v e d S a w m i l l R e c o v e r y 3 2. T h e C u t t i n g P r o b l e m 5 2.1 T e r m i n o l o g y 6 2.1.1 T h e B u c k i n g D e c i s i o n 7 2.1.2 T h e S a w i n g D e c i s i o n 8 3. O p t i m i z a t i o n T e c h n i q u e s A p p l i e d T o T h e c u t t i n g P r o b l e m . 1 0 3.1 L i n e a r P r o g r a m m i n g 11 3.2 S i m u l a t i o n M o d e l s 12 3.3L _ D y n a a i c P r o g r a m m i n g A p p l i e d To S i n g l e - S t e m M o d e l s . . 1 3 3.4 Summary 14 4. The B u c k i n g - S a w i n q P r o b l e m F o r m u l a t e d a s a L i n e a r P r o g r a m m e 15 4.1 D a n t z i g - W o l f e D e c o m p o s i t i o n 17 5. T h e C u t t i n g P r o b l e m F o r m u l a t e d As A D e c o m p o s i t i o n A l g o r i t h m 20 5.1 T h e L i n e a r P r o g r a m m e 22 5. 1. 1 S t a t e And D e c i s i o n V a r i a b l e s 24 5.1.2 A d d i n g A New P o l i c y V e c t o r 26 5.1.3 T h e S u b - P r o b l e m 29 5 . 2 T h e K n a p s a c k P r o b l e m 30 5 . 2 . 1 The D y n a m i c P r o g r a m m i n g R e c u r s i o n 32 6. tfcdelling T h e E u c k i n g - S a v i n g D e c i s i o n As A D e c e n t r a l i z e d D e c i s i c r P r o c e s s . , 37 V 6 . 1 C h a n g e s I n F o r m u l a t i o n 38 6 . 2 T h e S a w i n g D e c i s i o n 41 7 . l i n k i n g t h e S u b - P r o b l e m t o t h e L i n e a r Programme 45 7 . 1 T h e A u x i l l i a r y S u b - p r o b l e m - B O C K . O P T 45 7 . 2 B a n t z i g - H o l f e D e c o m p o s i t i o n W i t h MPSX 46 8. A T e s t P r o b l e m 49 8 . 1 C o m p u t a t i o n a l E x p e r i e n c e 51 8 . 1 . 1 A S t o p p i n g R u l e 54 8 . 1 . 2 I m p r o v i n g The E f f i c i e n c y Of The L . P 56 8 . 2 An E x p e r i m e n t To I m p r o v e C o n v e r g e n c e 58 8 . 3 I m p l e m e n t i n g t h e C u t t i n g S t r a t e g i e s . . . . . . . . . . . . . . . . 62 9 . Summary And C o n c l u s i o n s 63 B i b l i o g r a p h y • • 66 A p p e n d i x I . . 69 A p p e n d i x I I 76 v i L I S T OF FIGURES 1. F e l a t i c n Of D y n a m i c P r o g r a m i r i n g T e r m i n o l o g y T o The B u c k i n g Of A T r e e L e n g t h L o g 33 2. An A l g o r i t h m f o r t h e S o l u t i o n c f t h e D y n a m i c P r o g r a m m i n g R e c u r s i o n 36 3. T h e G e n e r a l A p p e a r a n c e c f t h e M a t r i x f o r t h e C o o r d i n a t i n g L i n e a r P r o g r a m m e 39 4. D e t e r m i n i n g O p t i m a l S a w i n g S t r a t e g i e s At E a c h S t a g e i n t h e D y n a m i c P r o g r a m m e , 43 5. F l o w c h a r t o f t h e D a n t z i g - W c l f e D e c o m p o s i t i o n Programme . 47 6 . S a w i n g o f a S h o r t L o g 50 7. T h e V a l u e c f t h e L . P . O b j e c t i v e F u n c t i o n V e r s u s t h e Number o f S i m p l e x I t e r a t i o n s 55 8 . T h e Number o f L o g C l a s s e s P r o c e s s e d By C u t t i n g S t r a t e q i e s C r e a t e d A t E a c h D e c o m p o s i t i o n 57 9 . T h e V a l u e o f t h e O b j e c t i v e F u n c t i o n V e r s u s T h e Number O f S i m p l e x I t e r a t i o n s F o r A c t i v i t i e s G e n e r a t e d By O p t i m a l A n d N c n - o p t i m a l S u b - p r o b l e m s 61 L I S T OP T A B L E S D i s t r i b u t i o n O f L u m b e r R e s u l t i n g Frcm The U n c o n s t r a i n e d C u t t i n g A c t i v i t i e s v i i i ACKNOWLEDGEMENTS The author wishes to thank h i s s u p e r v i s o r , Mr. G.G. Younq, f o r h i s patience and guidance throuqhout the author's years of graduate s t u d i e s . The author also wishes t o thank Dr. D.H. Will i a m s f o r suggesting the Dantzig-Wolfe decomposition technique as a method for analy z i n q optimal bucking-sawing d e c i s i o n s . F i n a l l y the author wishes to thank the F a c u l t y of F o r e s t r y fo r t h e i r f i n a n c i a l support and the U n i v e r s i t y Computing Centre f o r supplying the computer resources which made t h i s t h e s i s p o s s i b l e . 1 _I od u c t i o i] H i s t o r i c a l l y , changes i n conversion techniques i n the wood processing i n d u s t r y of North America have been slow, with emphasis on reducing labour c o s t s and i n c r e a s i n g production volume. Management p o l i c y has been t o promote change which maximized volume output and minimized labour cost per u n i t of time. T h i s was due, p r i m a r i l y , to two reasons. F i r s t , raw m a t e r i a l was r e l a t i v e l y inexpensive and hence expendable. Second, labour c o s t s and volume -through-put are easy t c measure and hence served a s a r e l a t i v e l y convenient measure of m i l l p e r f o r m a n c e . U n t i l r e c e n t l y , the value l o s t through maximizing volume r e c o v e r y r a t h e r t h a n m a x i m i z i n g d o l l a r y i e l d could n o t b e g u a n t i f i e d e f f i c i e n t l y . I n t h e l a s t few y e a r s t h e i n d u s t r y h a s f a c e d t h e e c o n o m i c p r e s s u r e o f i n c r e a s e d raw m a t e r i a l c o s t , i n c r e a s e d l o g g i n g a n d c o n v e r s i o n c o s t a n d l i m i t e d p r o d u c t v a l u e d u e t o c o m p e t i t i o n f r o m o t h e r p r o d u c t s . As a r e s u l t , many new t e c h n i g u e s a r e b e i n g u s e d b y t h e i n d u s t r y w h i c h p e r m i t more e f f i c i e n t u s e o f r a w m a t e r i a l . C h a n g e s h a v e b e e n made i n b o t h t h e h a r v e s t i n g o f t i m b e r a n d i n t h e c o n v e r s i o n o f l o g s i n t o lumber p r o d u c t s . Those c h a n g e s w h i c h h a v e s i g n i f i c a n t l y i m p r o v e d t h e f o r e s t i n d u s t r y ' s a b i l i t y t c d i r e c t e a c h p o r t i o n o f t h e l o g to i t s b e s t valued end p r o d u c t are d i s c u s s e d b e l o w . 2 •1.1 T r e e L e n g t h L o q g i r . q T h e i m p e t u s t o w a r d s t r e e - l e n q t h l o q q i n q was p r o m p t e d b y t h e r i s i n g c o s t o f woods l a b o u r i n t h e L a k e H e a d R e g i o n o f O n t a r i o . (Mason ( 1 9 7 1 ) ) . T h e d e v e l o p m e n t o f t h e a r t i c u l a t e d r u b b e r t i r e d s k i d d e r i n t h e l a t e 1 9 5 0 ' s a n d e a r l y 1 9 6 0 ' s p l u s t h e d e v e l o p m e n t o f l o n g - l o g h a u l i n g m e t h o d s h a s r e s u l t e d i n t h i s t e c h n i q u e b e i n g a p p l i e d i n many a r e a s o f N o r t h A m e r i c a where s m a l l d i a m e t e r t r e e s p r e d o m i n a t e . I t i s a n t i c i p a t e d t h a t t r e e - l e n g t h l o g g i n g w i l l c o n t i n u e t o be u s e d as more s e c o n d g r o w t h , e v e n a g e d s t a n d s a r e h a r v e s t e d . T h e b e n e f i t s o f t r e e - l e n g t h l o g g i n g a r e g a i n e d by e n a b l i n q t h e t o t a l < s t e m t o be h a n d l e d i n t h e c o n v e r s i o n o f t r e e s i n t o m a r k e t a b l e p r o d u c t s . I n a d d i t i o n t o l a b o u r s a v i n q s , h a n d l i n g l o n g l o g s o f f e r s g r e a t e r f l e x i b i l i t y i n o p t i m i z i n g v o l u m e a n d v a l u e y i e l d t h a n i s p o s s i b l e w i t h s h o r t e r l o g s b u c k e d i n t h e w o o d s . 1 .2 L o g M e r c h a n d i s e r s The a v a i l a b i l i t y o f t r e e - l e n g t h l o g s p l u s t h e n e e d t o o p t i m i z e p r o d u c t y i e l d f r o m t h e l o g r e s u l t e d i n t h e d e v e l o p m e n t o f l o g m e r c h a n d i s e r s . M e r c h a n d i s e r s e s s e n t i a l l y c e n t r a l i z e t h e l o g b u c k i n g d e c i s i o n . T h i s h a s s e v e r a l a d v a n t a g e s . The d e c i s i o n a s t o how a s t e m i s t o be c u t i s r e m o v e d f r o - t h e woods and o c c u r s i n a c o n t r o l l e d e n v i r o n m e n t . T h i s o f f e r s a means o f more a c c u r a t e l y c o n t r o l l i n g the s e l e c t i o n o f v a r i o u s p r o d u c t s t o be 3 cut and gives management the a b i l i t y to make r a p i d changes i n bucking i n s t r u c t i o n s as markets change. In a d d i t i o n , c e n t r a l i z a t i o n of bucking allowed the i n d u s t r y the c a p a b i l i t y of t a k i n g advantage of the t e c h n i c a l developments i n o p t i c a l scanners and automatic process c o n t r o l eguiproent. The r e s u l t i n recent years has been the development of automated l o q buckinq s t a t ions. 1 . 3 Improved Sawmill Recovery I n i t i a l attempts t o i n c r e a s e lumber r e c o v e r y r e s u l t e d i n the development of improved sawmill headrigs. Improvements i n c l u d e d c h i p p e r c a n t e r s and t h i n k e r f saws. The development of sawing equipment capable of c u t t i n g a c c u r a t e l y and with minimum k e r f l o s s , c r e a t e d a need f o r l o g c a r r i a g e s which could a c c u r a t e l y p o s i t i o n a l o g f o r c o n s i s t e n t c u t t i n g . Such eguipoent i s c apable of g r e a t e r p r e c i s i o n than the unaided o p e r a t o r can c o n s i s t e n t l y o b t a i n . The r e s u l t has been the development of process c o n t r o l systems which use o p t i c a l scanners and mini-computers t c p o s i t i o n d i g i t a l l y c o n t r o l l e d saw c a r r i a q e s . With e x i s t i n g process c o n t r o l systems i t i s t e c h n i c a l l y f e a s i b l e to automate many of the c u t t i n g d e c i s i o n s r e g u i r e d t o convert t r e e - l e n g t h l o g s i n t o marketable products. In a d d i t i o n to t h e i r process c o n t r o l f u n c t i o n , these l o g scanners and mini-computers are capable of providing d e t a i l e d production data. Such data provide the b a s i s f o r the management rep o r t s necessary for planning and coo r d i n a t i n g the i n d i v i d u a l c u t t i n q a c t i v i t i e s . The technoloqy e x i s t s to inplement and monitor c u t t i n q s t r a t e g i e s which maximize d o l l a r r e t u r n rather than maximize m i l l through-put. Becent advances ir. l o q handling and prccass c o n t r o l systems have made i t p o s s i b l e to implement more cctrplex c u t t i n g s t r a t e g i e s than was p r e v i o u s l y f e a s i b l e . This change i n technology has e s s e n t i a l l y expanded the number of a l t e r n a t i v e c u t t i n g s t r a t e g i e s which must be evaluated. The problem f a c i n g management i s to s p e c i f y the c u t t i n g i n s t r u c t i o n s which w i l l iraxiirize the d o l l a r r e t u r n from the a v a i l a b l e l o g supply. 5 2__lJ3__Cu t t i n c - _ P r R e q a r d l e s s o f w h e t h e r saws a r e p o s i t i o n e d a u t o m a t i c a l l y o r m a n u a l l y , a s e t o f c u t t i n q i n s t r u c t i o n s i s e s s e n t i a l . These i n s t r u c t i o n s s h o u l d , f o r t h e a v a i l a b l e l o q s u p p l y , p r o v i d e t h e most e c o n o m i c a l y i e l d c o n s i s t e n t w i t h m a r k e t demands and m i l l c o n s t r a i n t s . The c u t t i n q d e c i s i o n s r e q u i r e d t o c o n v e r t a t r e e - l e n g t h l o q i n t o m a r k e t a b l e p r o d u c t s a r e c o m p l e x and i n t e r d e p e n d e n t . Any one c u t r e s u l t s i n two or more p r o d u c t s . The v a l u e p e r u n i t volume o f t h e twc p r o d u c t s i s u s u a l l y d i f f e r e n t and t h e t o t a l v a l u e of t h e t w o p r o d u c t s d o e s n o t u s u a l l y e q u a l t h e v a l u e o f t h e o r i g i n a l p i e c e . E v e r y c u t consumes t i m e on a machine c e n t r e . Most cu t s make f u t u r e c o m m i t m e n t s on the use o f p r o c e s s i n g time on o t h e r machines i n t h e m a n u f a c t u r i n g p r o c e s s . F o r example, the d e c i s i o n to cut p e e l e r b o l t s f r o m a l o g i m p l i e s the a l l o c a t i o n of the b o l t s to a veneer m i l l and hence t h e consumption o f time on machines w i t h i n t h a t m i l l . S i m i l a r l y , a sawing p a t t e r n adopted a t the h e a d r i g i m p l i c i t l y assumes the use o f o t h e r machines such as edgers, trimmers and resaws i n the p r o d u c t i o n l i n e . D i f f e r e n t sawing p a t t e r n s consume va r y i n g amounts c f both h e a d r i g and downstream m a c h i n e t i m e . Machine time i s a l i m i t e d r e s o u r c e . The t i m e s p e n t on o n e cut excludes the use o f t h e same time t o make a n a l t e r n a t e c u t . T h u s , the c o s t of u s i n g a m a c h i n e c e n t r e t o m a n u f a c t u r e a p r o d u c t must i n c l u d e t h e o p p o r t u n i t y c o s t o f n o t u s i n q t h a t m a c h i n e t o m a n u f a c t u r e a l t e r n a t e p r o d u c t s . T h e r e f o r e , t h e p r o f i t a b i l i t y o f a c u t t i n q s t r a t e q y f o r a p a r t i c u l a r I c q c a n n o t be d e t e r m i n e d s c l e l y f r o m i t s own y i e l d d a t a and t i n e r e q u i r e m e n t s . T h e i n t e r d e p e n d e n c e b e t w e e n s u c c e s s i v e cuts and 6 t h e o p p o r t u n i t y c o s t a s s o c i a t e d w i t h u t i l i z i n g a l i m i t e d s u p p l y o f b o t h l o g s a n d m a c h i n e t i m e must be c o n s i d e r e d . I n a d d i t i o n , a s t h e p r i c e and demand f o r f o r e s t p r o d u c t s c h a n g e t h e r e l a t i v e p r o f i t a b i l i t y o f v a r i o u s c u t t i n g s t r a t e g i e s w i l l a l s o c h a n g e . T h u s i n o r d e r t o p r e s c r i b e e c o n o m i c c u t t i n q s t r a t e g i e s a p r o c e d u r e must be f o u n d t o i n t e g r a t e i n f o r m a t i o n on a v a i l a b l e l o g s u p p l y , p r o d u c t y i e l d , m a c h i n e p r o d u c t i v i t y a n d c a p a c i t i e s , s a l e s c o m m i t m e n t s , m a r k e t p r i c e s a n d m a r k e t d e m a n d . T h i s t h e s i s p r o p o s e s a m e t h o d o l o g y f o r s e a r c h i n g f o r c u t t i n g s t r a t e g i e s w h i c h w i l l m a x i m i z e t h e r e t u r n f o r a g i v e n l o g s u p p l y c o n s i s t e n t w i t h a l l t h e a b o v e m e n t i o n e d f a c t o r s . Two c r i t i c a l c u t t i n g d e c i s i o n s w i l l be a n a l y z e d , t h e b u c k i n g d e c i s i o n a n d t h e s a w i n g d e c i s i o n . The p r o b l e m o f d e t e r m i n i n q t h e b u c k i n g and s a w i n g s t r a t e g i e s w h i c h t o g e t h e r o p t i m i z e t h e r e t u r n f r o m a g i v e n l o g s u p p l y w i l l be r e f e r r e d t o a s t h e c u t t i n g p r o b l e m . 2. 1 T e r m i n o l o g y I n o r d e r t o p r o c e e d w i t h t h e d e s c r i p t i o n o f t h e p r o b l e m i t i s n e c e s s a r y t o d e f i n e some n o t a t i o n . The t e r m l o n g _ l c g r e f e r s t o l o g s w h i c h m u s t be c u t i n t o one o r more s h o r t e r l o g s b e f o r e t h e y a r e p r o c e s s e d i n a s a w m i l l . The l o n g l o g may be a _£S__I____fe l o g w h i c h was l i m b e d and t o p p e d i n t h e woods o r i t may be a l o g w h i c h h a s been c u t i n t h e p r o c e s s o f t r a n s p o r t i n g f r c m t h e woods t o the m i l l . The t e r n s h o r t _ l p g r e f e r s t o a l o g w h i c h w i l l n o t be c u t 7 a g a i n b e f o r e i t i s sawn a t a h e a d r i q . F o r n u r p c s e s o f d i s c u s s i o n i t w i l l be assumed t h a t s h o r t l o q s a r e p r o d u c e d at. a l o q m e r c h a n d i s e r o r or. a l o g deck i m m e d i a t e l y b e f o r e t h e l o q i s sawn i n t o l u m b e r , 2. 1. 1 The Bucking D e c i s i o n Eucking i s the c u t t i n g o f long l o g s i n t o one or more s h o r t l o q s . The c r i t i c a l bucking d e c i s i o n i s to determine the number of c u t s r e g u i r e d and to s p e c i f y the p o s i t i o n along the stem a t which t h e c u t s are to be made. The^pop u l a t i o n of short l o g s which r e s u l t from bucking are converted i n t o marketable products at a s a w m i l l h e a d r i g . The s h o r t l o g l e n g t h c o n s t r a i n s product l e n g t h and hence may l i m i t product value. Too long a l o g may r e s u l t i n decreased lumber r e c o v e r y due t o l o g taper, sweep o r crook. The p e n a l t y f o r making poor or i n c o r r e c t bucking d e c i s i o n s i s a l o s s of value from i n e f f i c i e n t u t i l i z a t i o n of the l o g and the p r o d u c t i o n o f a s h o r t l o g p o p u l a t i o n which cannot best meet the reguirements of the sawmill. 8 2.1.2 The S a w i n g D e c i s i o n A t t h e h e a d r i g t h e b u c k e d l o g s a r e sawn i n t o c a n t s , s l a b s and f l i t c h e s w h i c h a r e p r o c e s s e d i n t o l u m b e r f u r t h e r on i n t h e s a w m i l l i n g p r o c e s s . The d i m e n s i o n s o f t h e c a n t s , s l a b s and f l i t c h e s p r o d u c e d have a d i r e c t b e a r i n q on t h e p r o d u c t , and h e n c e v a l u e , o b t a i n e d f r o m e a c h l o g . A common c h a r a c t e r i s t i c o f s a w m i l l h e a d r i g s i s t h a t t h e saw c u t s w h i c h a r e made l o n g i t u d i n a l l y a l o n g t h e s t e m , c n c e s t a r t e d , must t r a v e r s e t h e stem i n a s t r a i g h t l i n e t o t h e o t h e r end o f t h e l o g . T h i s means t h a t l o g t a p e r , s w e e p , e c c e n t r i c i t y o f t h e l o g c r o s s s e c t i o n , and t h e l o c a t i o n o f d e f e c t w i l l h a v e a p r o n o u n c e d e f f e c t c n t h e d i m e n s i o n s a n d v a l u e o f t h e l u m b e r w h i c h c a n be sawn f r o m a l o g . The s a w i n g _ d e c i s i o n d e t e r m i n e s t h e l o c a t i o n a n d number o f saw c u t s w h i c h a r e t o b e p l a c e d i n t h e l o g a t t h e h e a d r i g . I n many i n d u s t r i a l s i t u a t i o n s s h o r t l o g s c a n be p r o c e s s e d a t more t h a n o n e c o n v e r s i o n c e n t r e a n d c a n b e p r o c e s s e d i n t o p r o d u c t s o t h e r t h a n l u m b e r . S u c h a s i t u a t i o n w o u l d a r i s e i n an i n t e g r a t e d c o n v e r s i o n c e n t r e w h e r e l u m b e r , v e n e e r , a n d wood c h i p s a r e m a n u f a c t u r e d . I n s u c h a s i t u a t i o n t h e s a w i n g d e c i s i o n w o u l d i n c l u d e p e e l i n g , w h o l e l o g c h i p p i n g o r s a w i n g i n t o l u m b e r a t c n e o r more m i l l s . E a c h m i l l w o u l d h a v e d i f f e r e n t d e s i q n c h a r a c t e r i s t i c s and w o u l d p r o d u c e d i f f e r i n g s i x e s a n d / o r t v p e s o f p r o d u c t s . I n t h i s s t u d y , t h e s a w i n g d e c i s i o n i m p l i c i t l y a s s u mes t h a t t h e l o g s a r e a l l o c a t e d b e t w e e n c o m p e t i n q c o n v e r s i o n f a c i l i t i e s . I t i s o b v i o u s t h a t t h e b u c k i n g and s a w i n g d e c i s i o n s are-i n t e r d e p e n d e n t . I n o r d e r t o d e t e r m i n e t h e h u c k i n q s t r a t e g y w h i c h y i e l d s t h e mix o f s h o r t l o g s t h a t w i l l p r o d u c e the- maximum 9 lumber value i t i s necessary t c know the saving p a t t e r n which w i l l be used to convert the loq i n t o lumber. S i m i l a r l y , given a l i m i t e d l o q supply of f i x e d c h a r a c t e r i s t i c s and l i m i t e d machine c a p a c i t i e s , the sawing d e c i s i o n cannot be determined i n i s o l a t i o n . The term c u t t i n g _ s t r a t e g j i m p l i e s both the tu c k i n g of lonq loqs i n t o short loqs and the sawing of the r e s u l t i n g short logs i n t o lumber products. A c _ t t i n g _ a c t i v i t y , i s the a p p l i c a t i o n of both bucking and sawinq d e c i s i o n s to an i n d i v i d u a l log or c l a s s of l o g s . Logs would be c a t e g o r i z e d by those a t t r i b u t e s which i n f l u e n c e d the t y p e a n d v a l u e of products which could be cut f r c m the logs. T h u s , t h e l o g s might be c l a s s e d by s p e c i e s , l e n g t h , t o p and b u t t d i a m e t e r s , g u a l i t y • a n d sweep. T h i s t h e s i s i s c o n c e r n e d w i t h analyzing a method f o r e v a l u a t i n g t h e c o m b i n e d b u c k i n g a n d s a w i n g d e c i s i o n s . A s s u c h t h i s t h e s i s may b e o f i n t e r e s t t o t h e o p e r a t i o n s r e s e a r c h a n a l y s t . F o r d e m o n s t r a t i o n p u r p o s e s t h e l o g s w i l l be i d e a l i z e d a s f r u s t a . T h e p r o b l e m s o f l o g s w e e p , c r o o k , e c c e n t r i c i t y , a n d d e f e c t a r e t o a l a r g e e x t e n t i g n o r e d . The p r a c t i c a l p r o b l e m o f i m p l e m e n t i n g t h e b u c k i n g a n d s a w i n g s t r a t e g i e s s u g g e s t e d by t h e m e t h o d o l o g y i s n o t a d d r e s s e d . 1 0 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ £_Ii_2y§§__2_Ii§__XQ_Ih^_Qi]^iiQ£J_?S2ble^ Techniques f o r determining the "op t i m a l " product y i e l d from loqs have been widely discussed in the l i t e r a t u r e since the e a r l y 1960's. However, none of the published s t u d i e s have e x p l i c i t l y considered the combined buckinq and sawing d e c i s i o n described above. Two approaches have been used to analyze buckinq and sawinq d e c i s i o n s , sinqle-stera and multi-stem models. Sinqle-stem models provide d e t a i l s o f a buckinq or sawing strategy which should be app l i e d to an i n d i v i d u a l l o g i n order t o maximize the r e t u r n from t h a t l o g . T h i s p r o b l e m h a s l a r g e l y been analyzed usinq s i m u l a t i o n o r d y n a m i c p r o g r a m m i n g models. A l t h o u g h there a r e no t e c h n i c a l p r o b l e m s a s s o c i a t e d w i t h a n a l y z i n g the combined b u c k i n g a n d s a w i n g d e c i s i o n s f o r a s i n g l e l o g , the p u b l i s h e d s t u d i e s h a v e a d d r e s s e d o n e o r t h e o t h e r o f t h e t w o d e c i s i o n s . M u l t i - s t e m m o d e l s a r e c o n c e r n e d w i t h a n a l y z i n g t h e o p t i m a l mix o f p r o d u c t s w h i c h s h o u l d be sawn f r o m a g i v e n l o g p o p u l a t i o n . T h i s p r o b l e m h a s b e e n l a r g e l y a n a l y z e d w i t h l i n e a r p r o g r a m m i n g m o d e l s a n d t o a l e s s e r e x t e n t s i m u l a t i o n m o d e l s . T h e m u l t i - s t e m m o d e l e x p l i c i t l y c o n s i d e r s t h e o p p o r t u n i t y c o s t s a s s o c i a t e d w i t h u t i l i z i n g a l i m i t e d s u p p l y o f resources s u c h as l o g s a n d / c r m a c h i n e a v a i l a b i l i t y . Both s i m u l a t i o n a n d l i n e a r p r o g r a m m i n g m o d e l s a r e l i m i t e d i n t h e number of a l t e r n a t i v e s t h e y c a n c o n s i d e r . H e n c e , t h e models are g e n e r a l l y f o r m u l a t e d t o analyze on o r t h e o t h e r o f t h e bucking or sawing d e c i s i o n . 11 3.1 L i n e a r Programming Perhaps the most e x t e n s i v e l y used technigue a p p l i e d tc the a n a l y s i s cf c u t t i n g s t r a t e g i e s f o r the multi-stem problem has been l i n e a r programming (L.P.). Smith and H a r r e l l (196 1) a p p l i e d the t e c h n i g u e to t h e problem of s e l e c t i n g the bucking s t r a t e g i e s w h i c h m a x i m i z e d t h e r e t u r n t o the l o g g i n g c o n t r a c t o r . For each long l o g category a l i m i t e d number of bucking a l t e r n a t i v e s were e n u m e r a t e d . R e s t r i c t i o n s were p l a c e d on the a v a i l a b l e l o g supply a n d o n t h e n u m b e r s o f s h o r t logs t h a t could be s o l d . A l i n e a r p r o g r a m m i n g c o d e was u s e d t o s e l e c t the f e a s i b l e set of bucking a l t e r n a t i v e s w h i c h m a x i m i z e d t h e c o n t r a c t o r s p r o f i t . A s i m i l a r f o r m u l a t i o n was u s e d by J a c k s o n a n d Smith (1961) to a l l o c a t e s h o r t l o g s t o a l t e r n a t e s a w i n g p a t t e r n s such that an optimum mix o f l u m b e r p r o d u c t s was p r o d u c e d . R e s t r i c t i o n s were placed o n t h e a m o u n t o f l u m b e r t h a t c o u l d be s o l d . I n o r d e r t o u s e a l i n e a r p r o g r a m m i n g m o d e l t o s e l e c t t h e s e t c f a l t e r n a t i v e s w h i c h o p t i m i z e s a n o b j e c t i v e f u n c t i o n i t i s n e c e s s a r y t o e n u m e r a t e a s e t o f a l t e r n a t i v e s f o r e v e r y l o g c a t e g o r y . I n t h e o r y t h e L.P. s h o u l d be s u p p l i e d w i t h a l l f e a s i b l e a l t e r n a t i v e s . I n p r a c t i s e an a r b i t r a r y s u b - s e t o f a l t e r n a t i v e s i s s u p p l i e d a n d t h e I.P. s e l e c t s the combination of a l t e r n a t i v e s w h i c h m a x i m i z e s t h e o b j e c t i v e f u n c t i o n w h i l e s a t i s f y i n g l i n e a r c o n s t r a i n t s . A l t h o u g h p r e s e n t computer technology permits l i n e a r programmes w i t h a l a r g e number of a l t e r n a t i v e s , i t has not been p o s s i b l e t o formulate r e a l i s t i c models which inco r p o r a t e the large number of a l t e r n a t i v e s necessary t o e v a l u a t e the combined bucking and sawing d e c i s i o n . The s i z e o f t h e p r o b l e m p l u s t h e 12 n e c e s s i t y o f e n u m e r a t i n g i n a d v a n c e a s e t o f f e a s i b l e a l t e r n a t i v e s h a s made s u c h l i n e a r p r o q r a m m i n g m o d e l s c o m p u t a t i o n a l l y i n f e a s i b l e o r u n e c o n o m i c a l to s o l v e . 3 . 2 S i m u l a t i o n M o d e l s C o m p u t e r s i m u l a t i o n m o d e l s i n c o r p o r a t i n q t h e l c q i c n e c e s s a r y t o d e t e r m i n e s u c e s s i v e saw c u t s h a v e b e e n u s e d t o i n t e q r a t e d a t a on l o g g e o m e t r y and s a w i n g t e c h n o l o g y . S u c h m o d e l s h a v e b e e n u s e d t o a n a l y z e c u t t i n g s t r a t e q i e s f o r b o t h s i n g l e l o q s and I c q p o p u l a t i o n s . U n l i k e l i n e a r p r o q r a m m i n q m o d e l s , s i m u l a t i o n m o d e l s do n o t f o l l o w any w e l l d e f i n e d s t r u c t u r e a n d t e n d t o be a d h o c i n n a t u r e . T h e y h a v e a n a d v a n t a q e o v e r L . P . m o d e l s i n t h a t t h e y c a n h a n d l e c o m p l e x i n t e r a c t i o n s b e t w e e n v a r i a b l e s i n t h e s y s t e m . H o w e v e r , s i m u l a t i o n i s n o t a n o p t i m u m s e e k i n q t e c h n i q u e . S i m u l a t i o n m o d e l s u s u a l l y o u t p u t some m e a s u r e o f p e r f o r m a n c e a n d t h e most a p p r o p r i a t e a l t e r n a t i v e i s d e t e r m i n e d b y i n s p e c t i o n a f t e r t h e m o d e l h a s b e e n u s e d t o s i m u l a t e t h e p r o b l e m u n d e r v a r i o u s a s s u m p t i o n s . M o s t o f t h e s i m u l a t i o n m o d e l s c o n s t r u c t e d t o a n a l y z e s a w i n g s t r a t e g i e s h a v e been o f t h e s i n g l e s tem v a r i e t y , ( H a l l o c k a n d L e w i s (1971 a n d 1 9 7 3 ) , Cummins a n d C u l b e r t s o n ( 1 9 7 2 ) ) . H a l l o c k and L e w i s u s e d s i m u l a t i o n t o d e t e r m i n e t h e b e s t p l a c e m e n t c f a q i v e n saw p a t t e r n w i t h i n a l o g c r e s s s e c t i o n . The y i e l d f r o m t h e i n d i v i d u a l l o g s was u s e d t o d e t e r m i n e t h e " b e s t " p l a c e m e n t o f t h e p a t t e r n . T h e r e was no a t t e m p t t o m o d e l t h e i n t e r a c t i o n 13 r e s u l t i n g frcn; the processing of a population of logs at a headrig. Several authors have applied simulation models to the multi-stem problem. (McAdoo (1969) and Aune (1973)). Aune used a simulation model to analyze the flew of material through a sawmill. Predetermined sawing strategies were implemented at the headrig. S t a t i s t i c s were calculated on the inte r a c t i o n of the res u l t i n g cants, slabs and f l i t c h e s at selected downstream machine centres. While Hallock and Lewis' model i s e s s e n t i a l l y a single stem model they reported t h e c a p a b i l i t y of determining the best sawing pattern and i t s position within the log subject to s a l e s constraints on lumber products. They did not discuss how t h e constraint was i m p o s e d on t h e model. T h e a p p l i c a t i o n o f s i m u l a t i o n m o d e l s t o t h e b u c k i n g p r o b l e m h a s b e e n l i m i t e d t o o b s e r v i n g t h e p o p u l a t i o n o f s h o r t l o g s t h a t r e s u l t s f r c m a p p l y i n g a n a s s u m e d b u c k i n g p o l i c y t o a q i v e n p o p u l a t i o n o f l o n g l o g s . T h i s t e c h n i q u e i s o f t e n a p p l i e d i n i n v e n t o r y c o m p i l a t i o n p r o q r a m m e s . 3 . 3 D y n a m i c P r o q r a m m i n q A p p l i e d T o S i n q l e - S t ' e m M o d e l s D y n a m i c p r o q r a m m i n q h a s b e e n suggested as a method o f determining o p t i m u m b u c k i n g strategies for a single l e g . (Boyd and Young (1969), L e a c h (1969), Pnevmaticos and Mann (1972)). Unlike the l i n e a r programming model suggested by Smith and H a r r e l l , a dynamic programming formulation of the bucking problem does not require the enumeration of a set of feasi b l e 14 p o l i c i e s from which an optimum subset i s s e l e c t e d . Instead, the dynairic programme c o n s i d e r s , i n an e f f i c i e n t manner, a l l p o s s i b l e bucking a l t e r n a t i v e s and s e l e c t s the optimum st r a t e g y . However, u n l i k e L.P., dynamic programming cannot e f f i c i e n t l y handle the i n t e r a c t i o n s inherent i n formulating an optimum bucking s t r a t e g y f o r a given population of long l o g s . The a d d i t i o n of c o n s t r a i n t s to a dynamic programming model s i g n i f i c a n t l y i n c r e a s e s the computational e f f o r t required to obtain a s o l u t i o n and, i n f a c t , may make the for m u l a t i o n i n t r a c t a b l e . 3 . 4 Summary T h e r e a r e many p u b l i s h e d s t u d i e s which suqqest t e c h n i q u e s f o r a n a l y z i n g b u c k i n g o r s a w i n g s t r a t e q i e s f o r s i n g l e l o q s . D y n a m i c p r o g r a m m i n g h a s b e e n u s e d t o g e n e r a t e a n d a n a l y z e o p t i m a l , b u c k i n g d e c i s i o n s f o r i n d i v i d u a l l o q s . S i m i l a r l y , c o m p u t e r s i m u l a t i o n m o d e l s h a v e b e e n used t o analyze a l t e r n a t e s a w i n q d e c i s i o n s f o r s i n g l e - s t e m s . However, t h e p r o b l e m o f d e t e r m i n i n g o p t i m a l b u c k i n g and sawing d e c i s i o n s f o r a U n i t e d l o g s u p p l y a n d l i m i t e d s a w m i l l c a p a c i t y has b e e n l e s s s u c c e s s f u l l y e v a l u a t e d . F o r m u l a t i n g the combined bucking-sawing p r o b l e m a s a l i n e a r p r o g r a m m i n g model i s a t t r a c t i v e but the l a r g e number o f a l t e r n a t i v e s make such a for m u l a t i o n i n t r a c t a b l e . 15 u. l _ _ _ B _ c _ i _ _ _ _ _ _ _ f l _ _ _ _ _ _ l a s a_ L i _____ ? r c_rararne C o n s i d e r a s a w m i l l t h a t m a n u f a c t u r e s l u m b e r and c h i p s f r o m a q i v e n s u p p l y o f t r e e - l e n g t h l o g s . The management p r o b l e m i s t o d e t e r m i n e t h e b u c k i n g and s a w i n g s t r a t e g i e s w h i c h m a x i m i z e t h e r e t u r n t o t h e m i l l , s u b j e c t t o c o n s t r a i n t s on m a c h i n e p r o d u c t i v i t y a n d c a p a c i t y , l i m i t e d l o g s u p p l y and s a l e s c o m m i t m e n t s f o r l u m b e r p r o d u c t s . T h i s p r o b l e m c a n be f o r m u l a t e d a s t h e l i n e a r m a t h e m a t i c a l p r o g r a m m i n g p r o b l e m ; f i n d n o n - n e g a t i v e m a x i m i z i n g t h e f o r m : N y = Z r x J n n n = l <<4-1) S u c h t h a t : N z n=l a x > b mn n — m m = 1, (4-2) w h e r e : i s t h e r e g u i r e m e n t o r a v a i l a b i l i t y l e v e l f o r c o n s t r a i n t ( p r o d u c t o r r e s o u r c e ) m. a i s t h e t e c h n i c a l c o e f f i c i e n t ( p r o d u c t s nun p r o d u c e d , r e s o u r c e s consumed) f o r c o n s t r a i n t m r e s u l t i n g f r o m c u t t i n g s t r a t e g y n. x i s t h e number o f l o g s t o w h i c h c u t t i n g s t r a t e g y n n i s a p p l i e d . r i s t h e r e t u r n f r c m u s i n g c u t t i n q s t r a t e q y n. n 'he t e r m c u t t i n g _ s t r a i m p l i e s b o t h t h e b u c k i n q o f l o n g I o c s 16 i n t c s h o r t l o g s a n d t h e s a w i n g o f t h e r e s u l t i n g s h o r t l c q s i n t o p r o d u c t s . E v e r y f e a s i b l e c u t t i n q s t r a t e g y f o r a g i v e n l o n g l o q i s c o n s i d e r e d t o be a n a c t i v i t y . A m a t h e m a t i c a l p r o q r a m r o i n q c o d e i s u s e d t o s e l e c t t h e s u b s e t o f a c t i v i t i e s w h i c h o p t i m i z e t h e o b j e c t i v e f u n c t i o n w h i l e m e e t i n g t e c h n o l o g i c a l and s a l e s r e s t r i c t i o n s . I n r e a l i t y s u c h m o d e l s a r e h a r d t o c o m p o s e . T h e d e t e r m i n a t i o n o f t h e t e c h n i c a l c o e f f i c i e n t s , a , f o r new mn b u c k i n g a n d s a w i n g a l t e r n a t i v e s may be e x p e n s i v e a n d t i m e c o n s u m i n g . I n a d d i t i o n , a s t h e number o f b u c k i n g and s a w i n q a l t e r n a t i v e s i n c r e a s e s , t h e l i n e a r p r o g r a m m i n g m o d e l may p r o v e t o b e u n e c o n o m i c a l t o s o l v e . T h e p r o b l e m o f s e l e c t i n g , f o r g i v e n p r o d u c t v a l u e s , t h e o p t i m u m b u c k i n g a n d s a w i n g s t r a t e g i e s f o r i n d i v i d u a l l o g s h a s b e e n s u c c e s s f u l l y d e t e r m i n e d w i t h d y n a m i c p r o g r a m m i n g a n d c o m p u t e r s i m u l a t i o n m o d e l s . I n f a c t m i n i - c o m p u t e r s w i t h o p t i c a l s c a n n i n g d e v i c e s h a v e b e e n p r o g r a m m e d t o s o l v e t h i s p r o b l e m i n r e a l t i n e o n a p r o d u c t i o n b a s i s . T h e l i m i t a t i o n o f o p t i m i z i n g t h e r e t u r n f r o m i n d i v i d u a l l o g s i s t h a t c o n s t r a i n t s o n s a l e s demand a n d t h e o p p o r t u n i t y c o s t a s s o c i a t e d w i t h u s i n g f i n i t e r e s o u r c e s a r e n o t e x p l i c i t l y c o n s i d e r e d . I d e a l l y t h e b u c k i n g a n d s a w i n g s t r a t e g i e s a p p l i e d t o a l e g p o p u l a t i o n s h o u l d y i e l d a n o p t i m a l r e t u r n t o t h e m i l l c o n s i s t e n t w i t h t h e c o n s t r a i n t s i m p o s e d b y s a l e s c o m m i t m e n t s a n d s a w m i l l c a p a c i t y . The D a n t z i g - W o l f e (1960) d e c o m p o s i t i o n p r i n c i p l e f c r l i n e a r p r o g r a m m e s s u g g e s t s t h a t t h e p r o c e s s o f d e t e r m i n i n g o p t i m a l c u t t i n g s t r a t e g i e s s u b j e c t t o c o n s t r a i n t s 'may be s i m u l a t e d ss a d e c e n t r a l i z e d d e c i s i o n p r o c e s s . 17 4 ,1 D a n t z i g - W c l f e D e c o m p o s i t i o n C o n s i d e r t h e p r o b l e m o f d e t e r m i n i n g a s e t c f c u t t i n g s t r a t e g i e s w h i c h y i e l d s a n o p t i m u m mix o f p r o d u c t s s u b j e c t t o c o n s t r a i n t s , as a two l e v e l p l a n n i n g p r o c e s s . L e v e l one i s a manager who c o o r d i n a t e s t h e s a w m i l l p r o d u c t i o n a n d s a l e s . l e v e l two i s t h e p r o d u c t i o n p e r s o n n e l r e s p o n s i b l e f o r s e l e c t i n g t e c h n i c a l l y f e a s i b l e b u c k i n g and s a w i n g s t r a t e g i e s f o r i n d i v i d u a l l o g s . S t a r t i n g w i t h a s e t o f c u t t i n g a l t e r n a t i v e s w h i c h a r e m u t u a l l y f e a s i b l e a n d meet a l l c o n s t r a i n t s i m p o s e d f r o m o u t s i d e t h e s y s t e m , t h e c o o r d i n a t o r f o r m u l a t e s an o p e r a t i n q p l a n . He u s e s t h i s p l a n t o d e t e r m i n e w h i c h p r o d u c t s a r e i n s h o r t s u p p l y a n d w h i c h r e s o u r c e s a r e u s e d t o c a p a c i t y . He t h e n o f f e r s a s y s t e m o f p r e m i u m c h a r g e s a n d b o n u s e s ( p r i c e s ) t o t h e o p e r a t i n q p e r s o n n e l i f t h e y c a n d e t e r m i n e a new c u t t i n g s t r a t e g y f o r i n d i v i d u a l l o g s w h i c h i s p r o f i t a b l e w i t h o u t r e g a r d t o w h e t h e r o r n o t i t i s f e a s i b l e i n t e r m s o f o v e r a l l s a w m i l l c a p a c i t y , l i m i t e d l o g s u p p l y , o r m a r k e t c o m m i t m e n t s . T h e new c u t t i n g s t r a t e g i e s n e e d o n l y be f e a s i b l e i n t e r m s o f b e i n g p h y s i c a l l y f e a s i b l e t o i m p l e m e n t ( i . e . t e c h n i c a l l y f e a s i b l e ) . T h e c o o r d i n a t o r c o m b i n e s t h e s e new c u t t i n g s t r a t e g i e s w i t h h i s p r e v i o u s a l t e r n a t i v e s t o g e n e r a t e a new o p e r a t i n g p l a n . U s i n g t h i s i m p r o v e d o v e r - a l l s o l u t i o n he g e n e r a t e s a r e v i s e d s e t o f p r i c e s w h i c h a r e a g a i n o f f e r e d t o t h e o p e r a t i n g p e r s o n n e l . T h e p r o c e s s c o n t i n u e s u n t i l t h e o p e r a t i n g p e r s o n n e l a r e u n a b l e t o d e t e r m i n e a new t e c h n i c a l l y f e a s i b l e c u t t i n q a l t e r n a t i v e w h i c h i s p r o f i t a b l e a c c o r d i n g t o t h e c u r r e n t p r i c e s o f f e r e d by t h e c o o r d i n a t o r . T h e j o b o f c o o r d i n a t o r can be s i m u l a t e d a s a l i n e a r 18 programming model. The problem of generating a new cutting a c t i v i t y involves the solution of an a u x i l i a r y problem of the type currently being solved to optimize the return from i n d i v i d u a l logs. The system of prices reguired to optimize the sub-problem i s available as part of the simplex computational procedure. The i t e r a t i v e process i s f i n i t e . (Dantziq and Wolfe (1960), Wclfe (1960), Dantzig ( 1963)). The Dantzig-Wolfe decomposition algorithm for l i n e a r programmes can be summarized as follows: 1. Model the constraints on sawmill capacity, leg supply, and sales commitments as a linear programming problem. Consider only a s u f f i c i e n t number of a c t i v i t i e s to s a t i s f y 2. 2. Select an i n i t i a l basic f e a s i b l e solution to the L.P. 3. Dse the simplex algorithm to determine the current optimum solution to the L. P, 4. Generate the system of prices from the L.P's dual variables. 5. Solve a sub-problem to determine a new a c t i v i t y (cutting p o l i c y ) , i f one exists, which w i l l improve the L.P. according to the current 19 prices found i n 4, If such an a c t i v i t y cannot be found STOP. The current L.P. solution is optimal and cannot be improved. If an improved a c t i v i t y i s found, continue. 6. Add the new a c t i v i t y (pclicy vector) to the L.P. an d GO TO 3. In the next chapter a l i n e a r proqramminq model suitable, for applyinq the Dantzig - W o l fe decomposition p r i n c i p l e to the prcblem cf selecting o p t i m a l buckinq strategies for a population o f l o n g l o g s w i l l be d i s c u s s e d . I t w i l l also be demonstrated t h a t t h e s u b - p r o b l e m w h i c h supplies the L.P. with new a c t i v i t i e s , ( s t e p 5 a b o v e ) , i s eguivalent to finding optimal b u c k i n g s t r a t e g i e s f o r a s i n g l e l o g . 20 __________________?_!£__ ____________________ ______^ In t h i s chapter the application of the Dantzig-Wclfe decomposition p r i n c i p l e for l i n e a r programmes to the problem of qenerating optimal strategies for cuttinq long legs into products w i l l be discussed. It w i l l be shown that the correct sub-problem tc solve i n order to generate a new cuttinq alternative which w i l l improve the current L.P. solution i s an integer programming problem, solvable by dynamic programming. For purposes of demonstration, a s i m p l i f i e d formulation of the bucking-sawing problem w i l l be discussed. Consider the problem of cutting long logs i n t o shorter lengths in order to meet reguirements for short logs at minimum cost. Formulating the problem as a minimum cost problem subject to requirement constraints avoids the problem of havinq to determine the value of each short log. Hence, for t h i s s i m p l i f i e d example, only the bucking decision i s considered. For each long log there i s one or more bucking strategies t o be considered. Each cutting strategy yields short logs at a cost egual t o the cost o f the parent log. This type of problem i s often referred t o as a cutting stock problem 1. A standard l i n e a r programming formulation of t h i s problem involves providing i n advance a l l possible cutting strategies *The cutting stock problem i s sometimes referred to as the Trim Problem in the l i t e r a t u r e . Seme of th? early work on this problem was done i n the paper industry where paper r o i l s are s l i t to meet customer requirements. The major economic consideration i s to minimize the trim loss. Hence the term "Trim Problem". 21 for each lcnq loq lenqth. A l i n e a r programming code is then used to select the sub-set of a c t i v i t i e s which optimized the objective function while meeting customer requirements for short logs. There are two facto r s which make t h i s formulation of the bucking problem impractical. F i r s t , i s the larqe number of a c t i v i t i e s which res u l t from enumerating a l l combinations of bucking strategies for each parent log c l a s s . The solution of a problem considering a r e a l i s t i c number of long log lengths and cutting strategies may te beyond present computer capacity or may reguire an excessive amount of computer time. The second factor i s the necessity of s e l e c t i n g an integer value for each a c t i v i t y . The second factor can be handled by approximatinq an integer so l u t i o n from a non-integer solution. I f the model i s imperfect 1 then f o r a l l p r a c t i c a l purposes such an approximation r e s u l t s i n a solution which i s s u f f i c i e n t l y close to optimum. The combinatorial nature of the f i r s t f a c t o r i s more d i f f i c u l t to handle. I t was not u n t i l Gilmore and Goirory (1961) developed t h e i r technigue f o r delaying the generation of a c t i v i t i e s f or the l i n e a r programme that solutions could be e f f e c t i v e l y obtained for reasonably sized cutting stock problems. Gilmore and Gomory demonstrated that Dantzig-Wolfe decomposition could be used to delay the generation of columns ( a c t i v i t i e s ) f o r the l i n e a r programme. The procedure avoids the necessity of working -Ihe model i s imperfect in the sense that constraints are approximations. the problem 22 with, a l l possible a c t i v i t i e s in the l i n e a r programs e. The L.P. calculates a l t e r n a t e l y with an m X _ matrix (the basis inverse) and the dynamic programme sub-problem generates new columns as reguired. The Gilmore-Gomory algorithm w i l l be explained by considering a s i m p l i f i e d l i n e a r proqramminq formulation of the cutting stock problem. The constrained derivative notation of Wilde and Beightler ( 1 9 6 7 ) i s introduced t c motivate the explanation cf Dantzig-Wolfe decomposition and to demonstrate the role of the L.P.'s dual variables. It w i l l be shown that the dual variables can be interpreted as a system of prices from which the imputed worth of a new a c t i v i t y to the L.P. can be calculated. I n i t i a l l y only the bucking decision w i l l be considered. A model suitable for the log bucking-sawing problem encountered i n the forest industry w i l l be discussed in the next chapter. 5.1 The Linear Programme Consider the cutti n g stock problem formulated as a standard l i n e a r programming problem. The problem i s to f i l l an order for s p e c i f i e d products at minimum cost. A c t i v i t y vectors represent s p e c i f i c cutting strategies applied to s p e c i f i c parent stock. Each a c t i v i t y produces one or mere products at a cost egual to the cost cf using the parent stock. There i s no cost associated with changing cutting patterns. The notation and explanation follows Wilde and Beightler. 23 The problem i s to find non-neqative x n ndnimizinq the f c r rr.: N y = E c x (5-1) 2 , n n n = l Such that: N E a x > b ; m = l , , M (5-2) mn n — m n = l where: b i s the order quantity requirement cf product in. m a i s t h e q u a n t i t y o f product m r e s u l t i n q from mn c u t t i n q s t r a t e q y n. x i s t h e number o f t i m e s cuttinq strateqy n i s n u s e d . c i s t h e c o s t o f c u t t i n q s t r a t e q y n . n T h e H c o n s t r a i n t e q u a t i o n s i n e q u a t i o n (5-2) c a n b e r e p l a c e d b y e q u a l i t y c o n s t r a i n t s b y a d d i n q M v a r i a b l e s . T h e p r o b l e m now i s t o f i n d n o n - n e q a t i v e x (k = l , . . , N+M) w h i c h m a x i m i z e e q u a t i o n (5-1) s u b j e c t t o t h e e q u a l i t y c o n s t r a i n t s N E a x - x„,, = b ; m = 1 M (5-3) mn n N+m m n = l There b e i n q fl l i n e a r independent equations there are well defined methods of se l e c t i n q K variables tc form an i n i t i a l basic f e a s i b l e s c l u t i o a . 2U 5.1,1 State And Decision Variables The set of N+fl variables i n equation (5-3) can be a r b i t r a r l y partitioned into N decision variables _ n and M state variables s • Decision variables can be manipulated f r e e l y m while t h e _=ta_L_____i_bles adjust i n response to chanqes in the decisions. The variables which formed the i n i t i a l f e a s i b l e s o l u t i o n to equations (5-1) and (5-3) can be renumbered one to M and c a l l e d the state variables. The remaininq N decision variables are set to zero. T h e state variables can always be expressed as a l i n e a r function o f t h e decisions: N s = 8 - _ a d (5-U) n = l where a a n d B a r e u n i q u e c o n s t a n t s . T h e tableau u s e d i n t h e mn m s i m p l e x p r o c e d u r e f o r s o l v i n q l i n e a r proqrammes e x p r e s s e s t h e s t a t e v a r i a b l e s i n t e r m s o f t h e d e c i s i o n v a r i a b l e s . A t e a c h i t e r a t i o n o f t h e s i m p l e x a l q o r i t h n a p a i r o f s t a t e a n d d e c i s i o n v a r i a b l e s i s i n t e r c h a n q e d ( i . e . a c u r r e n t s t a t e v a r i a b l e b e c o m e s a d e c i s i o n v a r i a b l e a n d a d e c i s i o n v a r i a b l e b e c o m e s a s t a t e v a r i a b l e ) . E a c h i t e r a t i o n ( t a b l e a u ) o f t h e s i m p l e x m e t h o d p r o d u c e s a b a s i c f e a s i b l e s o l u t i o n . Expressinq t h e o b j e c t i v e f u n c t i o n i n t e r m s o f t h e s t a t e a n d decision variables as: y = v c s + _ c d (0 3) J ... , m m • ° n n m = 1 n=l and d i f f e r e n t i a t i n q with respect to feasible perturbations of the decision variables, yields the decision d e r i v a t i v e : 6y 5d m = E c 5s + c n m n 1 1 1 = 1 Sd c n (5-6) ' where f j c means a derivative constrained to f e a s i b l e perturbations. Substituting (5-4) into (5-6), y i e l d s : 6 ) M (5"?) — — = c - E c a r , c n m mn od ' m=l n Equation (5-7) qives the decision derivative r e l a t i v e to the current set of states. I t indicates whether a change in the value of the corresponding decision variable w i l l increase or decrease the objective function. Given the basic f e a s i b l e solution to (5-1) and (5-3) the problem i s to f i n d a non-basic (decision) variable, i f one e x i s t s , which w i l l improve the current s o l u t i o n . I f such a variable cannot be found then the current s o l u t i o n i s optimal. 2 6 5 . 1 . 2 Adding A New Policy Vector Given that an optimal solution to the l i n e a r proqramrae has been determined, consider the c u t t i n g a c t i v i t y x which was e not considered in the o r i g i n a l l i n e a r programming problem (5-1). The a c t i v i t y can be defined as the column vector: ( c x , a x , e e ie e x J Me e The problem i s to determine i f the i n c l u s i o n of t h i s a c t i v i t y would improve the current optimal solution obtained for the o r i g i n a l problem. I f x would have been a decision v a r i a b l e , in the ie i t h constraint row would be: 6s d , i n the f i n a l tableau, then i t s c o e f f i c i e n t , a e ie a. i e 6 s . — l 6d = _ m 6 s . — i • 6s -m m 6d (5-8) = _ a . a i m me m where the summation m i s over the H s t a t e v a r i a b l e s , s , which m formed the the i n i t i a l b a s i c f e a s i b l e s o l u t i o n 1 . The a a r e im the elements of the i n v e r s e of the b a s i s , B _ l , and map the i n i t i a l t a b l e a u e n t r i e s , a , i n t o the f i n a l t a b l e a u e n t r i e s , im a . The e f f e c t of a s m a l l change i n the new d e c i s i o n v a r i a b l e , ie d e can be c a l c u l a t e d from (5-7) and (5-8) as: V a r i a b l e s are being renumbered depending cn the role they play as state or decision variables. The subscript i i s indexed over the state variables in the current optimal tableau. The subscript m i s indexed over the state variables in the i n i t i a l f e a s i b l e tableau. 27 6y 6d = c £ c. E a . a x i n m e i m ( 5 - 9 ) Re_.abell.inq the i state variables 1, ,M and remembering that m i s indexed over the state variables in the i n i t i a l tableau then (5-7) and (5-9) can be combined to y i e l d : If 6y 6d 6y 6d M = c - E a ( c -e , me m m=l 6y 6s m (5-10) i s negative then the Kuhn-Tucker non-negativity condition (a necessary condition for a minimum) i s violated and the basic feasible solution i s non-optimal and can be improved by bringing d e into the state set. The term c m 6y 6s (5-11) m i s the dual variable for the mth primal constraint and can be l a b e l l e d n . A dual v a r i a b l e for a given primal f e a s i b l e solution represents the i m p l i c i t value of the marginal unit of resource m. Row (0) of the simplex tableau i s the negative vector of dual variables. A new a c t i v i t y can be used i n a solution that w i l l improve the current objective value i f and only i f : M - E m=l a TT me m < 0 (5-12) or, M £ a TT > C (5-13) me m e m=l An i n t u i t i v e i n t e r p r e t a t i o n cf (5-13) would be that the l i n e a r programming problem defined by (5-1) and (5-2) could be improved i f an a c t i v i t y vector could be found such that the return to the problem imputed by the dual variables exceeds the ccst to the objective function. If the simplex solu t i o n procedure i s used to minimize (5-1) subject to <5-2) and a basic f e a s i b l e solution e x i s t s , then the simplex procedure t e s t s each decision variable u n t i l one i s found which can replace one of the current state variables. I f the objective function i s to be improved the entering decision variable must s a t i s f y (5-13). A conventional l i n e a r programming formulation of the cutting stock problem would reguire the simplex procedure to search a large number of non-basic variables to f i n d a cutting a c t i v i t y , i f one exists, which w i l l improve the current solution. Gilmore and Gomory have shown that i f the reguired cutting a c t i v i t y e x i s t s i t can be generated by solving a sub-problem. 2 9 5.1.3 The Sub-Problem It car. be concluded that there exists an a c t i v i t y cuttinq parent stock length L into products of length lm that can pro f i t a b l y be used i f and only i f there are non-negative integers aj ,.., a s a t i s f y i n g : a i l i + + a 1 < L f 5 - 1 4 ) 1 m m — and I T i ai + + TT a > C (5-15) m m T h e ffi !•••> ^ m a r e the d u a l variables which are av a i l a b l e as p a r t c f t h e n o r m a l s i m p l e x c o m p u t a t i o n a l p r o c e d u r e . a_ i s t h e q u a n t i t y ( i n t e g e r ) o f p r o d u c t m g e n e r a t e d b y t h e c u t t i n q a c t i v i t y . G i s t h e c o s t o f i m p l e m e n t i n g t h e c u t t i n q a c t i v i t y . One m e t h o d o f d e t e r m i n i n g w h e t h e r o r not t h e r e a r e n o n - n e q a t i v e i n t e q e r s s a t i s f y i n q (5-14) a n d (5 -15 ) w o u l d b e t o f i n d i n t e g e r s s a t i s f y i n q (5-14) f o r w h i c h TT i a i + + TT a m m i s m a x i m i z e d . I f s u c h i n t e q e r s d i d not s a t i s f y (5 -15) then none w o u l d . H e n c e t h e p r o b l e m o f f i n d i n q a new variable to enter the basis i n the s i m p l e x alqorithm for the cuttinq stock problem can be e x p r e s s e d as an inteqer proqramminq problem. The inteqer programming problem i s of the knapsack type and can be formulated as a dynamic programming recursion. 30 5.2 The Knapsack Problem The generalized knapsack 1 problem arises in two ways. If a portion of space i s being loaded with objects, each having a value, the knapsack problem i s to find the most valuable packing subject to a t c t a l volume or weiqht l i m i t a t i o n . Alternately, i f a portion of space i s being cut into pieces cf d i f f e r e n t value, the knapsack problem i s to find the most valuable cutting stategy. An example of a one-dimensional knapsack problem of the l a t t e r type i s the problem of cutting a lonq log length i n t c the most valuable products. I n t u i t i v e l y the problem can be considered to be the problem of f i t t i n g products of length l i into a box the length of the long log. The products f i t t e d into the box are placed end-to-end and the t o t a l length of the products cannot exceed the box length. A multi-dimensional knapsack problem would consider a d d i t i o n a l l i m i t a t i o n s such as width and length which would allow a more complex packing of products into the box. At the moment we are only considering the single dimension knapsack problem. Gilmore and Gomory have shown that the problem of generating a new column vector for a l i n e a r programming formulation of the cu t t i n g stock problem 1 can be overcome by solving a knapsack problem. The a c t i v i t y vector reguired by the L . P . i s the solution to the problem of cutting a si n g l e parent stock length in an optimal manner. JThe name "knapsack" problem was suggested by Dantzig (1957). An alternate name, the "loading" problem was given by Bellman (1957). Cited in Garfinkel and Nemhauser (1S72). 31 The p r o b l e m o f g e n e r a t i n g a new c o l u m n v e c t o r f o r t h e l i n e a r p r o g r a m m i n g p r o b l e m i s t h e i n t e g e r p r o g r a m m i n g p r o b l e m o f f i n d i n g t h e a m j m a x i m i z i n g t h e f o r m : M (5-16) s u c h t h a t : Z = E 7T m mi m=l M E 1 a . < L <5"17> m mj — m=l w h e r e : l m i s the length of product m (short log). L i s the length of the parent stock material (long log). amj ^ s quantity (integer) of product m r e s u l t i n g from cutting strategy i . Such an integer programming problem can, in p r i n c i p l e , be solved by dynamic programming. 5.2.1 The Dynamic Programming Recursion From a given long loq of length L , there i s a f i n i t e number cf short logs which can be bucked. The dimensions, and possibly value of a short log, w i l l depend cn the pcrticn of the long leg from which i t i s bucked. Assume that the long log can only be cut at certa i n locations along i t s length. For the mcment. assume that these locations are equidistant apart and that the distance between these locations can be made a r b i t r a r i l y small. Some rules for selecting locations w i l l be discussed la t e r . Each of these cutting locations w i l l be numbered one to M st a r t i n g from-one end of the log. Tn order to conform to dynamic programming terminology each of these numbered lo c a t i o n s w i l l be referred to as a stag.e. Each stage implies a location along the tree length stem. From knowing the location of the stage i t i s possible to define a unigue state. The state variables, combined with information cn log length, supply a l l the information required to determine the value of a short log. The state variables w i l l be the log diameter, log guality etc. In order to simp l i f y notation a l l the state variables w i l l be referred to as a . That i s , o contains a l l the information needed to value m m the r e s u l t i n g short leg i f a cut i s made at stage l o c a t i o n _>. Let F ( a ) be the maximum value that can be obtained i n m m eguaticn (5-16) i f the long log was only m stage units in length. Consider each stage of the tree lenqth loq in turn. Given that the long log i s only m staqe units i n lenqth, the decision at staqe m i s at which previous staqe (location) should the loq have been cut in order to obtain the maximum value 33 ( f i g u r e 1) . DECISIONS-<|> = 2 H <()=1 m-2 m-1 m m+1 J STAGES 0 - M Figure 1. Relation of dynamic programming terminology to the bucking of a tree length log, C a lculating F (a ) re c u r s i v e l y for each possible long log m m length, m, y i e l d s the recursive equation: F (a ) = Max { r.( a ) + F .(a ,)} m m . _ <p m m-d> m-a> <p = 0 , . , m (5-18) m = 0 , , M where: cj> i s the decision variable. r.(a ) i s the return from a short Icq of lenqth <p m u n i t s when c u t m-(f> . s t a g e l o c a t i o n m and 34 F (a ) i s i s t h s maximum return frcro a Icq m-<f> staqe units i n length. (i . e. the remainder of the loq). Using the i n i t i a l conditions Fo(Oo)=0 a n a r 0=0 t equation (5-18) i s i t e r a t e d for a l l M stages. It has been assumed in equation (5-18) that m , the location at which saw cuts i n the lonq loq are to be considered, takes on integer values from 0 to M . By choosinq any appropriate unit of measure the i n t e r v a l at which m i s evaluated can be made a r b i t r a r i l y small. If m i s incremented in too small a step s i z e the computational burden of evaluating (5 -18) may be excessive. The maximum step size would normally be less than or egual to the minimum difference between short log lengths and must be a common denominator of the lcng leg and a l l short log lengths*. Thus, i f tree length logs were being bucked into saw logs the step s i z e would conceivably be one or two feet. . Although F M ( o"M) i s the highest value obtainable from a log of length M there remains the problem of determining the bucking policy that gave t h i s value. This i s accomplished by performing a backward pass a f t e r the recursive eguation has been solved for a l l <{> and m . There are a number of methods of accomplishing t h i s backward pass. One method i s to define an indic a t o r array P(m) for a l l m . ipnevmaticos and Mann i n c o r r e c t l y defined the staqe length as the shortest product length. 3 5 The values of the array are defined as: P (m) = A ; m = 0 M m where <t> i s the value of the decision variable which maximizes m (5-18) at stage m . Once the maximum return, f M ^ Q M ^ ' ^ S determined, the index associated with P(M) i s referenced. I f the index i s <f> then a short log of length <f> units i s cut from the long log. The buck would be made at stage location ~ i - <j). The next index of i n t e r e s t i s the index P(M-cj) ) and the process continues u n t i l the entire cutting pattern i s known. One possible algorithm for the evaluation of (5-18) i s given in figure 2. 36 INPUT TABLE OF PRICES cp m m 0 F (m) *• 0 (()•*- 0 Figure 2. An a l g o r i t h m for the solution of the dynamic programming r e c u r s i o n . 3 7 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ In the previous chapter a procedure was discussed that avoids the d i f f i c u l t y of too many cuttinq alternatives i n the l i n e a r programming formulation of the cutting stock problem. When the L.P. reached the stage of looking f o r a new cutting a c t i v i t y which would improve the current solution, instead of looking over a vast e x i s t i n g c o l l e c t i o n of a c t i v i t i e s to select a useful one, a useful a c t i v i t y i s created by solving an au x i l i a r y problem. It was shown that the correct a u x i l i a r y problem to solve in order to generate a new cutting a c t i v i t y for the L.P. i s a generalized one-dimensional knapsack function. In t h i s chapter the changes reguired to adapt the Gilmore-Gomory algorithm to the log bucking-sawing problem encountered i n the forest industry are described. The changes required include: (a) maximizing the return to the m i l l rather than minimizing the cost of meetinq s p e c i f i e d requirements, (b) deteraininq the value of short loqs r e s u l t i n g from the bucking decision by considering the sawinq decision, and, (c) modifyinq the formulation to consider resource l i m i t a t i o n s such as machine capacity and loq supply. These changes can be accomplished by modifying the formulation of the lin e a r programme and by making changes in the dynamic programming sub-problem. 3 8 6.1 Changes In Formulation Two changes i n the l i n e a r programming formulation are required to maximize revenue minus cost and to handle the problem of f i n i t e resources. Incorporating the changes i n the L.P. matrix reguires modifying the objective function and adding transfer rows to ensure that a l l products produced are consumed. In addition capacity r e s t r i c t i o n s are added f o r each limited resource consumed by cutting a c t i v i t i e s . The l i n e a r programme becomes the problem of finding non-negative X j which maximize the form: y = H ( v. P - c. x, ) <6~1> ... k k 3 3 k 3 Such that: P, - I u, . x. = 0 * (6 - 2 ) I u, . x. > b, k kl> 3 - k t . x. < r 3 D — where: x. i s the number of times cutting stateqy j i s used. C j i s the cost of implementinq cuttinq strategy i . i s the quantity of product k (lumber cr chips) produced by cuttinq strategy j . t_. i s the quantity of a limited resource consumed by cutting strateqy -j, r i s the total a v a i l a b i l i t y c f the limited 3 9 resource. P i s the quantity of product k sold, k vk i s the value of product k. i s the requirement f o r product k. The qeneral appearance of the resulting l i n e a r programming matrix i s shown in figure 3. The block U contains a l l the " c l • ' c j I -1 I = o • u | « • * -1 I = o * i I £ r + 1 I > bi • | • • * + 1 Figure 3. The General Appearance of the Matrix of the Coordinatinq Linear Programme. products, u k j , created b y the i cuttinq strategies. The L.P. now includes prices (costs) for the l i m i t e d resource as well as f o r the product requirements. The cutt i n g a c t i v i t y returned by the column generating sub-problem w i l l contain c o e f f i c i e n t s > u k j , and t j . The product c o e f f i c i e n t s , U , can be expressed as , . = e. . • a. . k i (6-3) where a i s the quantity (integer) of short loq i produced by i j cuttinq strategy j and e . i s the volume of product k (lumber k 1 or chips) sawn from short Icq i . Maximizing revenue minus cost as opposed to minimizing cost dees not a f f e c t the column generating sub-problem. The objective of the sub-problem i s s t i l l to find a cutting a c t i v i t y which has an imputed worth to the L.P. which exceeds the cost to the L.P. of using the a c t i v i t y . The addition of constraints on limited resources adds addi t i o n a l costs to those cutting strategies which consume the resource. The system of prices generated by the coordinating l i n e a r programme w i l l include a charge for the l i i r i t e d resources. Remembering that problem of generating, i n the a u x i l i a r y problem, a new a c t i v i t y for the L.P. w i l l be the problem of f i n d i n g non-negative SL^ , which maximize the form: u, . = e. . a. . , then the k j k i i ] I K Z E TT, e, . a . .+ IT t . - c . i-1 k-1 k k l 1 D r 3 J (6-U) such that: E 1. a . . < L i = l i I J -(6-5) where: TT. are the dual variables for the k product k constraints. TT i s the dual variable for the U n i t e d r resource. .1 " i s the length of short log i . 41 consumed by cuttinq strateqy. "j. a i s the quantity of short loq i produced by i j cuttinq strateqy j. e i s the quantity of product . k (lumber and k i chips) produced from short loq i . L i s the lenqth cf the parent stock material. Cj i s the cost of iirplementinq cuttinq strateqy If the l i m i t e d resource i s used to capacity, 77 w i l l be r neqative, otherwise i t w i l l be zero. Cnce the column i s qenerated the c a l c u l a t i o n proceeds as in the simple cuttinq stock case. Constraints on limited resources would include r e s t r i c t i o n s on the a v a i l a b i l i t y of parent loq material, l i m i t a t i o n s on machine capacity or r e s t r i c t i o n s e on the marketinq of lumber or chips. 6.2 The Sawinq Decision The coordinatinq l i n e a r proqramme maximizes the revenue derived from the sale of lumber and chips less the variable cost of production. The L . P . qenerates a system of prices (bonuses and charqes) b y which i t judqes the p r o f i t a b i l i t y of cuttinq strateqies qenerated by the dynamic proqramminq s u b - p r o b l e m . The wcrth cf a buckinq strateqy t o t h e L.P. i s d e t e r m i n e d by t h e v a l u e cf t h e products t h a t c a n be sawn from s h o r t I c q s r e s u i t i r . q f r o m the buckinq decision l e s s t h e c o s t c f c o n s u m i n g f i n i t e r e s o u r c e s . U2 Given a parent l o q K staqe units i n lenqth w i t h $ f e a s i b l e decisions, the return from each decision i s determined by t h e sawinq strategy which can be applied t o t h e r e s u l t i n q short l o q . The problem i s to determine the sawing strategy f o r a single short log which y i e l d s the maximum product value (figure 4). Such an optimal sawing strategy f o r a s i n g l e log can be determined by computer simulation, two-dimensional dynamic programming or empirical y i e l d studies. The sawing strategy must be obtained f o r every f e a s i b l e decision at each stage i n the dynamic programming column generating sub-problem. The dynamic programming recursion i s solved once for each cutting strategy returned to the L . P . F o r t h i s reason computational e f f i c i e n c y may dominate the decision as tc which procedure i s used to determine the optimal sawing strategy. In the test problem discussed in chapter 8 a table lookup procedure i s used to select the "best" of f i v e alternate sawing patterns. The table values were calculated from empirical tests and as such they i m p l i c i t l y considered any reductions in yield which resulted frcm log sweep, e c c e n t r i c i t y or defect in the test logs. The y i e l d s for alternate sawing strategies could have been generated from an appropriate simulation model or, a simulation model could be run under d i r e c t c c n t r c l of the dynairic programming bucking model. Such a simulation m o d e l would have to be e f f i c i e n t l y e x e c u t e d as i t must be a c c e s s e d f o r e a c h f e a s i b l e decision at e a c h s t a g e of the dynamic prcqrarming r e c u rsion. I f t h e coordinating L.P, was m o d e l l i n g m u l t i p l e c cn ve r si or. j*-m-(j) -*| J ,0 CHIPS LUM BER AND CHIPS F m = r , ( a ) + Temp <p m m-cp m-q> i<5 L U M B E R A N D C H I P S F = r (a ) + 0 Temp (J) m Figure 4. Determining optimal sawing strategies at each stage in the dynamic programme. The sawing decision must be evaluated for each f e a s i b l e bucking decision <cj>) at each staqe (•) • f a c i l i t i e s then a simulation model for each f a c i l i t y would b available to the dynamic proqramme. If a loq merchandiser i ava i l a b l e , short logs can be independently allocated t diffe r e n t conversion f a c i l i t i e s . Otherwise, each f a c i l i t competes for the entire long Icq. The two cases would b modelled d i f f e r e n t l y . If only long loqs, as opposed to short loqs, can b allocated then the sub-problem would return, to the L.P., a cuttinq strategy for each feasible Icq a l l o c a t i o n . This would involve solving the dynamic prcqramminq recursion for each fe a s i b l e a l l o c a t i o n . A d i f f e r e n t sawinq simulator would be accessed each time the recursion i s evaluated. If short loqs are allocated then i t would only be necessary to sclve equation (5-18) once, but several sawing simulators would be accessed at each decision and each staqe of the dynamic programme. The return from each decision would be the greatest value returned by the simulation models. The set of state variables for the dynamic programme would have to be expanded to include an a l l o c a t i o n variable. The programme which solved the dynamic programming recursion would e f f e c t i v e l y c a l l a programme which would supervise the running of the simulation models. The simulation supervisor would return to the dynamic programme a l i s t of products generated by the most p r o f i t a b l e conversion f a c i l i t y plus an appropriate value for the a l l o c a t i o n state variable. 45 7^_Lin_kinc] the_S ub^Prohlem to t h_3_Linea r_Proaramff e In the next chapter a test problem i s formulated to demonstrate the application of the G i l more-Gomory cuttinq stock algorithm to the problem of deteririninq optimal bucking and sawing p o l i c i e s for a given supply of long logs. In order to demonstrate the procedure two computer programmes were written; a programme to perform the Dantzig-Wolfe decomposition and a programme to determine an optimal bucking and sawing strategy for a si n g l e log. 7.1 The A u x i l l i a r y Sub-problem - BOCK.OPT The dynamic programming recursion discussed i n section 5.2.1 was programmed i n Fortran IV. C o l l e c t i v e l y , the suite of sub-programmes reguired to implement the algorithm are referred to as J30CK. OPT. For given lumber and chip prices BUCK.OPT determines the bucking and sawing strategy f o r a single log which maximizes product value minus the cost of the a c t i v i t y . The cost of a cutting a c t i v i t y i s the cost of the parent log plus the cost of the time on the headrig reguired to implement the sawing strategy. The "best" sawing strateqy for each short log resu l t i n g from the bucking decision i s determined by evaluating five possible sawing strategies plus whole loq chipping. The product yield for each of the alternate sawing strategies i s determined through a table lookup procedure. The 46 tables were derived from empirical y i e l d studies. Depending on the option selected BUCK, CPT maximizes the net value of products sawn at the headriq or the net value cf the expected outturn of saleable products after falldown. The source l i s t i n g for BUCK.OPT i s given in appendix I. 7.2 Dantzig-Wclfe Decomposition With MPSX The programme i m p l e m e n t i n g the Dantzig-Wolfe decomposition algorithm i s s i m i l i a r t o the one described by Williams ( 1 9 7 7 ) . T h e p r o g r a m m e u s e s t h e IBM Mathematical Programming System EXended (MPSX) s y s t e m (IBM, 1972) and the Fortran programme BUCK.OPT d e s c r i b e d i n t h e p r e v i o u s section. A flowchart o f the d e c o m p o s i t i o n p r o g r a m m e i s g i v e n i n figure 5 a n d a l i s t i n g o f t h e MPSX programme i s g i v e n i n a p p e n d i x II. T h e p r o g r a m m e s t a r t s u n d e r c o n t r o l of MPSX. T h e L.P. m a t r i x i s r e a d f r c m a l i n e f i l e a n d s e t up on t h e p r o b l e m f i l e . A F o r t r a n p r o c e d u r e SDB1 w h i c h r e a d s in control p a r a m e t e r s a n d s e t s v a r i o u s f l a g s i s i n v o k e d . I h e MPSX Read Communications F o r m a t READCOMM s y s t e m (IBM, 1971a) i s used to transfer data b e t w e e n t h e MPSX and F o r t r a n programmes. On returning to MPSX t h e 1.P. i s o p t i m i z e d , the optimum basis i s saved on the problem f i l e , a n d t h e p i values (marginal values) of constrained commodities are loaded into MPSX variables. Control i s then transferred to the Fortran procedure SUS 2 which transfers c c r t r c l tc BUCK.OPT. EUCK.OPT obtains the marginal values for commodities 47 M P S X FOR T R A N Figure 5. F l o w c h a r t o f the D a n t z i g - W o l f e d e c o m p o s i t i o n programme ( a f t e r W i l l i a m s ( 1 9 7 7 ) ) . 48 consummed/generated by the L.P. from MPSX via PFACCOMM. The marginal values are used, to price the commodities qenerated or consumed cutting a single log. The Fortran programme selects long logs from a l i n e f i l e of log categories and determines the opt i n a l bucking and sawing strategy. If the optimal cutting strategy w i l l improve the current L.P. solution the strategy i s expressed as an L.P. vector and written to a l i n e f i l e i n the format of an MPSX REVISE f i l e . The Fortran procedure calculates the optimal cutting strategy for each long log category. A l l a c t i v i t i e s which w i l l improve the current L.P. solution are written to the REVISE f i l e . If an optimal cutting strategy which w i l l improve the L.P. i s not found a flag i s set. Cc n t r c l i s transferred back to the MPSX programme,• Under control of MPSX, two conditions are checked to determine i f the algorithm continues. F i r s t the no improvement f l a g i s checked. I f the no improvement fl a g i s set the current solution i s considered optimal and output procedures are invoked. Otherwise next the variable accumulating the number of decompositions i s examined. If the number of decompositions exceeds a maximum value s p e c i f i e d b y SUB1 the algorithm i s terminated. I f neither of these two conditions are met the new L.P. vectors i n the REVISE f i l e are added to the model cn the problem f i l e . The revised problem i s set up, the previous optimal basis i s restored and the problem i s optimized. The new pi values are selected and control i s again transferred t c the Fortran procedure. 49 8 . i_Test_Problem £ test problem was formulated tc ' demonstrate the application of the Gilmore-Gomory cuttinq stock algorithm t c the problem of determining optimal bucking and sawing p o l i c i e s for a giver, supply of long logs. For purposes of demonstration i t i s assumed that a si n g l e sawmill manufactures ditension lumber 1 and chips. Chips are produced as a by-product of lumber manufacturing and from a whcle leg chipper. The lumber products are sold as studs or random length dimension lumber. Marketing r e s t r i c t i o n s plus h i s t o r i c a l precedent have established d i s t r i b u t i o n s which such random lengths must follow. The through-put of the m i l l i s assumed to be constrained by the headrig capacity. The capacity of the whole leg chipper i s unrestricted. Only sawing strategies at the headrig are considered. .. Decisions made at machine centres downstream of the headrig r e s u l t i n the stock created at the headrig being cut into products of lesser dimension. This falldown i s a r e s u l t of cuts made to remove defect or to improve the grade recovery cf luirber products as well as a r e s u l t of operator error. For purposes of demonstration i t i s assumed that every product cut at the headrig r e s u l t s i n a known d i s t r i b u t i o n o f saleable products. Product grade i s not e x p l i c i t l y considered. The parent log supply consists o f a t o t a l o f nine hundred 135 lumber products are manufactured in dimensions cf 2X4,6,3,10 and 12 inches in even lengths from 8 to 2 4 feet. 50 and sixty-seven (967) loqs in forty-four (44) loq cateqories. A buckinq and sawinq strateqy applied to an i n d i v i d u a l lor.q loq yield s a mix of products to be cut at the headriq. Each buckinq and sawinq a c t i v i t y consumes a unigue quantity of headriq time depending on the number of short logs handled. 1 The headrig was assumed to be available for a maximum of 960 minutes. Two cuts are made i n each short log processed at the headrig. The sawing decision i s tc determine the nominal width (w) cf the centre cant (figure 6 ) . The side lumber i s resawn 2 X 4 A N D CHIPS Figure 6. Sawing of a short leg at the headrig. For the test problem, the sawing decision i s to determine the width (W) of the centre cant. into 2 X 4 . The cants are sawn at downstream cachine centres i n t o dimension lumber. The slabs are cenverted into 2X4 and chips. 1The headrig times are c a l c u l a t e d on t h e a s s u i r . r t i o n t h a t i t takes 2 seconds to l o a d a l o g on t h e c a r r i a g e , ar:i 3 s e c o n d s t c orientate and secure t h e l o q p r i o r t o each, saw c r , Two saw c u t s are made i n each log and t h e c a r r i a g e t r a v e l s a t 95 1 p e r r . i n u t e . 5 1 The problem i s to select buckinq and sawinq a c t i v i t i e s which maximize the net return to the m i l l ' while s a t i s f y i n q constraints on availa b l e parent Icq supply, headriq capacity and lenqth d i s t r i b u t i o n of marketable products. A buckinq and sawinq a c t i v i t y implies the cuttinq of a lonq loq from a specified loq category in a specified manner. The cost of the a c t i v i t y i s the cost of the parent log. Each a c t i v i t y reduces the number of lonq logs available in a speci f i e d Icq cateqory, consumes headrig time and generates products at the headrig which are processed into products of lesser dimension at downstream machine centres. The r e s u l t i n g lumber i s sold in sp e c i f i e d length d i s t r i b u t i o n s . 8.1 Computational Experience The test problem was programmed and run on the University of B r i t i s h Columbia's IBM 370/168 operatinq under HTS (Michigan Terminal System). The i n i t i a l f e a s i b l e s o l u t i o n for the L.P. was obtained by usinq EUCK.OPT to determine the optimal cuttinq strateqy for each loq cla s s . BOCK.OPT maximized the value of products produced after falldown. There was no cost associated with usinq the headriq. I t was assumed that lonq logs could be purchased for $30 per cunit. The d i s t r i b u t i o n of lumber produced i f a l l 967 lonq Ions were cut accordinq to their incividuaiy optimal cuttinq strategy is shewn in table 1. This unconstrained optimal strateqy yields 52 LENGTH 2X4 2X6 2X8 2X10 2X12 8 • 10' 12' 14' 16 • 18' 20' 22' 24' 10. 0 12.6 10. 4 19.0 23. 8 8. 8 9. 4 3.9 9. 0 24. 1 10.0 6. 9 . 9 11.3 26.7 ' 43.4 17.8 24.0 2.9 9,1 94. 0 0.0 54. 8 135.1 0.0 Table 1, Dis t r i b u t i o n of lumber products (MFBM) produced. after falldown i f the 44 i n d i v i d u a l l y optimal cuttinq strategies were applied to the parent Icq population. The t o t a l lumber production i s 283.88 MFEK. a net revenue of $12,558 and consumes 1147 minutes of headrig time. The optimal cuttinq strateqies for each cf the parent loq classes were entered as a c t i v i t i e s i n the L.P. model. The L.P. selected the combination of a c t i v i t i e s which maximized net revenue while meetinq constraints on headriq capacity and lumber lenqths. The cutting a c t i v i t i e s which i n d i v i d u a l l y yielded the maximum value f o r each log c l a s s , when combined y i e l d a constrained optimum of $1,754. The problem constraints l i m i t e d the L.P. to using 23 of the 44 possible cutting a c t i v i t i e s on 470 of the 967 long logs. The net revenue was reduced by $10,804. or 86?. . Starting from t h i s i n i t i a l f e a s i b l e solution the marqinal values of the lumber products and headrig time were selected and BUCK.OPT was used to generate cutting a c t i v i t i e s which would improve the current L.P. sol u t i o n . The new a c t i v i t i e s were combined with the o r i g i n a l ac t iv i t ies to form a new linear programming problem. The revised L.P, was optimized, new marqinal values were selected and BUCK, OFT was used to create 53 new cuttinq a c t i v i t i e s . This process was continued for 20 decent positions. After 20 decompositions the maximum net revenue was $1 1 , 668. and the t o t a l lumber production was 263.03 MFBH. The optimal strateqy was to produce 2X4 studs, and random lenqth 2X4 and 2X12's. The d i s t r i b u t i o n of lumber lenqths was constrained by the L.P, A l l 967 long logs were consumed. It i s i n t e r e s t i n g to note the d i f f e r e n t products generated by the constained and unconstrained optima. The unconstrained optimum strategy produced 2X4, 2X8, and 2X10's. The constrained optiffum only produced 2X4 and 2x12*s. While the c o n s t a i r t s may be u n r e a l i s t i c or unduly s i m p l i s t i c , the differences i n sawing strategies demonstrates the e f f e c t of optimizing the return from i n d i v i d u a l logs as opposed to optimizing the return from a population of logs. This i s more dramatically demonstrated when i t i s noted that the i n d i v i d u a l l y optimal strategies when subject to constraints had a value of only $1,754 while the constrained optimal strategy f o r a population of logs had a value of $11,668. An increase of 665%. Almost a l l the 44 log classes were processed by a single cutting strategy. Only 7 log classes were cut by 2 or more s t r a t e g i e s . 1 I t would be expected that a problem more complex than the test problem would r e s u l t i n more logs processed by multiple cutting strategies. iQne log c l a s s was b u c k e d and sawn t y 4 a l t e r n a t e s t r a t e g i e s , c l a s s e s by 3 s t r a t e g i e s , and 4 l o q c l a s s e s by 2 s t a t e g i e s . 54 8.1.1 A Stepping Rule In the test problem i t was found that the objective .function i n i t i a l l y improved very rapidly, and then the rate of improvement decreased as more decompositions were performed. Because of the large number of cutting strategies which are i m p l i c i t l y a v a i l a b l e , adding new cutting combinations at la t e r decompositions y i e l d s l i t t l e improvement to the L.P. objective function. The large number of cutting strategies i m p l i c i t l y available i s partly a function of the constraints i n the l i n e a r programming problem. In the test problem only the parent loq supply and the headrig capacity are s t r i c t l y constrained. The t o t a l guantity of product manufactured i s not e x p l i c i t l y constrained, the constraints only specify that lumber must be produced i n s p e c i f i e d length d i s t r i b u t i o n s . For t h i s reason there are a large number of cutti n g s t r a t e g i e s which s a t i s f y the product constraints while consuming nearly i d e n t i c a l guantities of headrig time. I f the test problem had been more highly constrained i t would be expected that the i n i t i a l rate of improvement would have been greater, although the computational e f f o r t at each decomposition may have increased. Although decomposition 20 had returned cutting a c t i v i t i e s which would improve the current I.P. solution i t was decided to terminate the algorithm after examining a plct. of the L.P. objective function value versus the number of decompositons (figure 7). If the model were allowed to continue the objective function would be improved. The dashed l i n e in figure 7 represents the unconstrained optimal return. This value was obtained bv using BUCK.OPT to 56 determine the optimal cutting strateqy for each icnq loq class, The value of each short leg was determined by selecting the sawing strategy which maximized the value of lumber produced after falldown. The unconstrained optimum provides an upper l i m i t for the L.P, objective function. After 20 decompositions the L.P. was within 1% of th i s upper bound. I t was decided that further computational e f f o r t was not warranted for the expected increase in the objective function. 8.1.2 Improving The E f f i c i e n c y Of The L.P. As the decomposition algorithm proceeds, columns qenerated by the sub-problem are added to the line a r programme. Columns generated by e a r l i e r decompositions are forced out of the basis by l a t e r columns (figure 8 a-d). In the example, as the L.P. i s augmented by new a c t i v i t i e s , those columns dropping out of the basis are retained as supplementary columns. If computer memory i s a problem i t may be necessary to pe r i o d i c a l l y delete columns from the l i n e a r programme. Dantzig (1963) suggested that a c t i v i t i e s which have the highest reduced cost could be dropped. A variation of Dantziq's suqqestion would be to drop those columns which have been non-basic for the qreatest number of decompositions. Alternately, at each decomposition a l l non-basic variables could be dropped from the matr i x. In addition to reducinq memory requirements the advantage of trimming the L.P. matrix is that a f t e r each decomposition N U M B E R O F L O N G L O G S ro co J> cn cn O m O 0 CO 1 -S 5 O z CO fO OJ I—' »—' cn »—» OJ —I CO f—• to ro o i s o o CD o o _ i _ ro o o CO o o ro O o m • O "0 O CO H o Z to CU cn cn co co o ro • co I—• 4S »—• cn y cn »—• CO »—• to ro o to o o J CO o CJ ro o o Q o co CD O cn O m O O •o O CO o Z CO to o m o o -a O co O z co ro o o J ro CO cn cn co to »—• o t—' »-» t—• ro »—* co •—• i—' cn CO t—• — J * CO I D ro o a m O o o CO CO 58 there are fewer non-basic a c t i v i t i e s to search in order to find a new optimal solution. This should reduce the computaticnal e f f o r t required to f i n d the new optimal solution after each decomposition. The disadvantage of trirnminq the matrix i s that ncr-tasic variables may become basic at l a t e r decompositions. I f non-basic vectors have been trimmed from the matrix the sub-problem w i l l be forced to create a vector nearly i d e n t i c a l to a vector i t had previously created. Thus trimming the matrix may increase the computational e f f o r t i n the sub-problem. No attempt was made in the t e s t problem to trim the L.P. matrix. However, just as vectors were added to the L.P. under FORTRAN control an algorithm could be programmed in FORTRAN to delete vectors from the matrix. 8.2 An Experiment To Improve Convergence At- each decomposition the dynamic programming sub-problem returns for each long log class the cutting strategy which yi e l d s the most improvement per unit increase i n the associated variable in the L. P., x_. , C a l l the rate of improvement r_. Although the sub-problem finds the cutting a c t i v i t y which maximizes r_. , i t does not address i t s e l f to the problem cf how big x. w i l l be a f t e r the simplex pivot step i s completed. The improvement in the L.P. objective function i s the product x • r . I t i s possible that an a c t i v i t y with a small rate cf j j improvement i f associated with a larqs x. could r e s u l t in a larqer improvement in the objective function than an a c t i v i t y 59 with a larqer rate of improvement and an associated small x It- i s not possible to know what the improvement in the objective function w i l l be u n t i l the simplex pivot step i s complete. The sub-problem returns, for each loq c l a s s , the cuttinq strateqy with maximum rate of improvement. The cuttinq strategies, although unique, tend to produce s i m i l a r products because each strateqy i s calculated usinq the same set of imputed values supplied by the L.P. One possible consequence of these strateqies producing nearly i d e n t i c a l products i s that th e i r corresponding a c t i v i t y l e v e l s , x , w i l l not bs very 3 large because each a c t i v i t y w i l l s a t i s f y the same constraints. I t i s possible that c u t t i n g strategies which had smaller rates of improvement but when considered as a group generated a diverse mix of products would be less constrained and would r e s u l t i n a greater increase i n the objective function. In order to t e s t t h i s hypothesis the sub-problen was modified so that once a cutting strategy was generated the imputed, worth of the products produced by the strategy were reduced by 50%. This was done on the assumption that the demand for these products would be s a t i s f i e d by the current cutting strategy and subseguent cutting strategies would tend to favour other products. Following such a strategy a l l the cutting a c t i v i t i e s would be "good", i . e . , they would a l l p o t e n t i a l l y improve the o b j e c t i v e function, but seme would be non-optinal, i . e . , they would not necessarily have the maximum rate of improvement. However, considered as a group, at each decompositon they would tend to offer the l i n e a r programme a selection of cutting a c t i v i t i e s which generated a diverse % i v. o f 60 prod yets. Figure 9 shows a plot of the L.P. objective function value versus the number of simplex i t e r a t i o n s for this schema. The s o l i d line shows the improvement i n the objective function i f the sub-problem generates optimal cutting strategies. The dashed l i n e r e s u l t s when the sub-problem returns "good", but not necessarily optimal, strategies which produce a diverse mix of products. For the test problem the sub-optimal a c t i v i t i e s i n i t i a l l y generated a faster rate of improvement in the L.P. objective than did the optimal a c t i v i t i e s . However, as the rate of improvement i n the objective function decreases the advantage cf generating sub-optimal a c t i v i t i e s decreases and generating optimal cutting s t r a t e g i e s becomes advantageous. This d e m o n s t r a t e s t h a t f o r some problems i t may be c o m p u t a t i o n a l l y a d v a n t a g e o u s t o g e n e r a t e " g o o d " b u t n o t n e c e s s a r i l y o p t i m a l c u t t i n g a c t i v i t i e s d u r i n g t h e i n i t i a l s t a g e s o f t h e d e c o m p o s i t i o n a l g o r i t h m . T h e s e n o n - o p t i m a l c u t t i n g s t r a t e g i e s w o u l d n o t n e c e s s a r i l y h a v e t o be g e n e r a t e d by a d y n a m i c p r o g r a m m i n g a l g o r i t h m a n d c o u l d p o s s i b l y b e g e n e r a t e d most e f i c i e n t l y by some a d h o c p r o c e d u r e . As t h e r a t e o f i m p r o v e m e n t i n t h e L . P. o b j e c t i v e function decreases then t h e o p t i c a l s u b - p r o b l e m c o u l d be s o l v e d . cn 61 cn ID ID o F i g u r e 9. The v a l u e o f t h e l i n e a r programme o b j e c t i v e f u n c t i o n v e r s u s t h e number o f i t e r a t i o n s f o r c u t t i n g s t r a t e g i e s g e n e r a t e d by o p t i m a l and n o n - o p t i m a l s u b - p r o b l e m s . Each v e r t i c a l b a r s i g n i f i e s a d e c o m p o s i t i o n . 62 8.3 Implementing the Cuttinq Strategies The decomposition algorithm s p e c i f i e s the number of loqs i n each parent log c l a s s to be processed by s p e c i f i e d cutting strategies. It would be necessary to implement such strategies with the aid of a process control system, p a r t i c u l a r l y i f multiple cutting strategies were tc be applied to the same parent log class. Such a control system would have to be capable of determining for each long log the log c l a s s i n which i t belcnqed and then implement the pre-determined cutti n g strategy. Cnce the guantitative goals for a p a r t i c u l a r log class have been rcet new cutting strategies could be evolved, These new cutting strategies would maximize the net revenue from the leg class. The commodity prices would be the set cf prices generated by the L.P. a f t e r the l a s t decomposition. The problem would be equivalent to solvinq the dynamic proqramuinq recursion solved by BUCK.OPT. These new strateqies would only be optimal i f the goals s p e c i f i e d by the l i n e a r prcqramme for each loq class had been iret. • 9. Summary And Conclusions Sawnill management faces the problem of determininq cutting instructions for an a v a i l a b l e log supply which provide a maximum return consistent with market demands for lumber products and m i l l constraints. The cutting i n s t r u c t i o n s must consider two interdependent decisions, the bucking decision and the saviinq decision. The return from a buckinq p o l i c y i s dependent cn the lumber products which can be sawn from the r e s u l t i n q short loqs. The. value of the lumber products i s , i n turn, p a r t i a l l y dependent on the dimensions of the short loq from which they were sawn. Technigues curren t l y applied to analyzing the bucking and sawing decision have not adeguately modelled the interdependence of the two decisions. Each decision has tended to be analyzed i n i s o l a t i o n . This t h e s i s proposes a methodology by which the combined bucking-sawing decision can be analyzed. Linear programming i s an a t t r a c t i v e technique for selecting a subset of buckinq and sawinq strateqies which maximize the return frcm a population of lonq loqs. The l i n e a r model i s optimum seekinq and i s well suited to handlinq constraints. In addition, as a by-product of the solution procedure, the ffcdel supplies information on the s e n s i t i v i t y of the solution to assumptions made within the ncdel. A conventional l i n e a r programming formulation of the cutting problem would require supplying the L.P. with a larqe number of alternate strateqies. The L.P. would se l e c t a sub-set of a c t i v i t i e s which Eaxitrizsd the objective function while satisfying the problem cot; stra i n t s . The d i f f i c u l t y i s that there are too many feasible cuttinq 64 a c t i v i t i e s which must be considered by t h e L.P. I t was not u n t i l Gilmore and Gomory used Dantzig-Wclfe decomposition t o d e l a y t h e generation of a c t i v i t i e s i n t h e li n e a r programme t h a t i t became fe a s i b l e t o model t h e s e l e c t i o n of optimal bucking and sawing a c t i v i t i e s a s an L.P. When, i n the simplex algorithm, the L.P. reaches t h e stage o f looking for a new a c t i v i t y which w i l l improve t h e solution, instead o f locking over a vast c o l l e c t i o n of e x i s t i n g a c t i v i t i e s t o select a useful one, a useful a c t i v i t y i s created by solving an a u x i l i a r y problem. I t was shown that the correct a u x i l i a r y problem t o solve in order to generate a useful column for the L.P. i s a knapsack function which can be solved by a dynamic programming recursion. The dynamic programme searches, i n an organized fashion, for bucking strategies which w i l l improve the current L.P. solution. The worth of any bucking strategy i s determined from the products which can be sawn from the r e s u l t i n g short log. The product outturn from a short log i s calculated by simulating alternate sawing strategies to f i n d the sawing a l t e r n a t i v e which r e s u l t s in the highest value. The value of the r e s u l t i n g products i s calculated using the p i values supplied by the simplex ccmputational procedure. The decomposition approach for analyzing t h e buckinq-sawing decision i s a t t r a c t i v e for two reasons. F i r s t i t i s not necessary to supply the L.P. with a v a s t number o f a l t e r n a t i v e bucking-sawing strategies i n advance. T h i s r e d u c e s t h e c o s t of generating t h e d a t a f o r t h e L.P, Second, when the L.P. i s searching f o r an optimal s o l u t i o n i t does not. have tc s e a r c h a 65 larqe number of existinq a c t i v i t i e s . I t can instead generate useful a c t i v i t i e s as required. The delayed column generating approach, by always workinq with the mXm basis inverse, makes i t feasible to solve problems which would be intractable i f formulated as conventional l i n e a r proqrammes. The procedure was demonstrated with a s i m p l i f i e d test problem in which a population of lonq loqs was bucked and sawn such that the return to a sawmill was maximized. The problem was constrained by the available loq supply, limited headriq capacity and r e s t r i c t i o n s on lumber lenqth. It was shown that buckinq and sawinq strateqies which were optimal for in d i v i d u a l legs qenerated poor solutions when they were combined under conditions of l i m i t e d m i l l capacity and market constraints. By using the delayed column generating approach i t was demonstrated that a set of cu t t i n q strateqies could be qenerated which i n d i v i d u a l l y were sub-optimal but when combined under a system of constraints produced a hiqher return than produced by the i n d i v i d u a l l y optimal s t r a t e q i e s . The buckinq and sawinq strateqies qenerated by the Dantziq-Holfe decomposition would be used by manaqement to formulate buckinq and sawinq quidelines which would best match the available l o q supply to the order f i l e . The res u l t i n q cuttinq strateqies would be implemented as decision rules for operatinq personnel or as programmed instructions for computer controlled saws at a log merchandiser or at the m i l l headrig. I t i s expected that new strategies wculd be evaluated as the order f i l e , product values or loq supply changed. 66 BIBLIGGBAFHY 1. Aune, J.E., 1973, The Application Cf Simulation Technique to the Study Of Sawmill Productivity, K.F. Thesis, Faculty of Forestry, University of B r i t i s h Columbia, pp 93. 2. BauJcstor. J.R., 1973, Product Selection: Peelers cr Sawlogs and Chips, in Modern Sawmill Techniques Vcl. 2: Proceedings cf the Second Sawmill C l i n i c , H.G, Lambert ed., M i l l e r Freeman Pub. Inc. , San Fran., C a l i f . , pp 57-73. 3. Eellman, B. E. and S.F. Dreyfus, 1972, Applied Dynamic Programming, Princeton University Press, Princeton, New Jersey, pp 363. 4. Bcyd, C.W. and G.G. Young, 1969, Forestry 471 Lecture Notes, Faculty of Forestry, University of B r i t i s h Ccluirbia, Unpublished. 5. Cooper L. and D. Steinberg, 1974, Methods and Applications of Linear Programming, W.B. Saunders Company, Philadelphia, PA, pp 434. 6. Cummins, L.K. and D.D. Culbertson, 1972, Sawmill Simulation For Maximizing Log Yield Values, For. Prod. Jour. , V c l . 2 2 , No. 1 0 , pp 3 4 - 4 0 . 7. Dantzig, G.B. , 1 9 6 3 , Linear Programming and Extensions, Princeton University Press, Princeton New Jersey, pp 6 3 2 . 8. , Dan_tzig, G. B. and P. Wolfe, 1960 , Decomposition P r i n c i p l e f o r Linear Programs, Operations Besearch, Vol. 8, pp 1 0 1 - 1 1 1 . 9. Dobie, J . and D . M , Wright, 1 9 7 2 , Conversion Factors f o r the Forest Products Industry i n western Canada, Dept. of the Environment, C. F. S. , West. For. Prod. Lab., Inf. Rep. VP-X-97, pp 60 . 10. G a r f i n k e l B.S. and G.L. Nemhauser, 1972, Integer Programming, John Wiley and Sens, New York, pp 427. 11 . Gilmore P. C. and R.E, Gomory, 1961, A Linear Programming Approach to the Cutting Stock Problem, Operations Research, Vol. 9, pp 849-859. 12. Gilmore P.C. and R.E. Gomory, 1963, A Linear Programming Approach to the Cutting Stock Problem - Fart II , Operations Research, Vol. 11, pp 863-836. 13. Gilmore P.C. and R.E, Gomory, 1965, Multistage Cuttinq Stock Problems of Two and More Dimensions, Operations Ersearch, Vol. 13, pp 94-120. 67 14. Gilroore P.C. and R.E. Gomcry, 1966, The Theory and Computation of Knapsack Functions, Operations Research, Vol. 14, pp 1045-1074. 15. Hallock, li . and D. W. Lewis, 197 1, Increasing Softwood Dimension Yield For Small Loqs - Best Opening Face, For. Prod. Lab., DSDA Forest Service Res. Paper FPL 166, Madison W i s c o n s i n . 16. Hallock, H. and D.W. Lewis, 1973, Best Openinq Face for Southern Pine, i n Modern Sawmilling Techniques Vol. 2: Proceed, of the 2ND Sawmill C l i n i c , H. Lambert ed., M i l l e r Freeman Pub. Inc., San Fran., C a l i f . , pp 204-225. 17. H i l l i e r , F. S. and G.J. Lieterman, 1967, Introduction To Operations Research, Holden-Day Inc., San Francisco, C a l i f o r n i a , pp 639. 18. I.B.M., 1971a, Mathematical Programming System Extended (MPSX) Read Communications (READCOMM) Program Description Manual, SH20-0960-0, IBM Corporation, White Pl a i n s , New York, pp 37. 19. I.B.M., 1971b, Mathematical Programming System Extended (MPSX) Control Language User's Manual, SH20-0932-0, IBM Corporation, White Plains, New York, pp 34. 20. I.E.M., 1972, Mathematical Programminq System Extended (MPSX) , and Generalized Upper Bounding (GUB) Program Description, SH20-0968-1, IBM Corporation, White Plains, New York, pp 344. 21. Jackson, N. D. and G.W. Smith, 1961, Linear Programming i n Lumber Production, For. Prod. Jour., Vol. 11, No. 6, pp 222-274 22. leach, H.A., 1969, Lecture to Fourth Year Harvesting Class, Faculty of Forestry, University of B r i t i s h Columbia, Unpublished. 23. Mason, H.C., 1971, North American Progress, i n Proceedings of the Wood Machinery Seminar - March 24-25, W.A. Post ed., University Of C a l i f o r n i a Forest Products Laboratory, Richmond, pp 152-172. 24. McAdoo, J.C., 1969, Computer Simulation of Small Log K i l l Processsing, For. Prod. Jour., Vol. 19, No, 4, pp 34-35. 25. Mead, W.J., 1966, Competition and Oliqopsonv in the Douglas F i r Lumber Industry, University of C a l i f o r n i a Press, Berkeley, C a l i f o r n i a . 26. Pnevmaticos, S. M. and S. H. Kar.n, 1972, Dynamic Programming in Tree Bucking, For. Prod. Jour., Vol. 22, No. 2, pp 26-30. 6 8 27. Smith, G.K. and C. H a r r e l l , 1961, Linear Proqramminq in Loq 'Production, Fcr. Prod. Jour., Vol. 11, No, 1, pn 8-11. 28. Eagner, H.M., 1970, P r i n c i p l e s of Management Science With Application to Executive Decisions, Prentice-Hall, Englewood C l i f f s , New Jersey, pp 555. 29. White, D.J., 1969, Dynamic Programming, Hclden-Day Inc., San Francisco, C a l i f o r n i a , pp 180. 30. Wilde, D.J And C.S. Beightler, 1967, Foundations of Optimization, Prentice-Hall Inc., Englewocd C l i f f s , New Jersey, pp 430. 31. Williams, D.H, 1977, Integrating Stand And Forest Models For Decision Analysis-, Ph. D. Thesis, Faculty of Forestry, University of B r i t i s h Columbia, Unpublished, pp 230. 32. W i l l i s t o n , E.M., 1976, Lumber Manufacturing: The Design and Operation of Sawmills and Planer M i l l s , K i l l e r Freeman Pub. Inc., San Fran., C a l i f . , pp 512 69 APPENDIX I The source l i s t i n g of the BUCK.OPT sub-proqracmes. C "BUCK.OPT" C C DYNAMIC PROGRAMMING SUB-PROELEM CALLED BY MPSX C IN CBEER TO GENERATE A NEW COLUMN VECTOR. C C JIM MCPHALEN C FACULTY OF FORESTRY C UNIVERSITY OF BRITISH COLUMBIA C MAY, 1975 C C C LOGICAL UNIT #2 FILE OF TREE LENGTH LOGS. C ' #3 REVISED L.P. DATA FILE. C #4 BUCKING POLICY REPORT WRITER FILE. C DIMENSION COEF(6, 24,99) , COF (6) , DIM (5) , FS(99), 1BUCK(99), YIELD(20,5), DJ(45), DIA(99), DV (2) , SYK (2) , 2RDIA{99) COMMON / BLK1/ YIELD, DJ, DIA, RDIA, CHIPDJ INTEGER STAGE, TDIA, POLICY (99) , GRP, LOAD(99) REAL LOG(44) DATA SIM/ *-«, 1 1 * / DATA DIH/ »04», »06', »C8', 110*, '12'/ LOGICAL * 1 CHAR(3) , TOP(2), PROD(2), XLEN(2) LOGICAL SWTCB, CHPSWT C C GET THE "SYSTEM" OF PRICES. C CALL GETARG(DJ(1) , DJ (2) ,DJ(3) ,DJ (4) ,DJ(5) ,DJ(6) ,DJ(7) , 1DJ(8) ,DJ(9) , DJ(10) ,DJ(11) ,DJ(12) ,DJ(13) ,DJ(14) , 2DJ (15) ,DJ (16) ,DJ (17) ,DJ ( 18) ,DJ (19) , DJ(20) , DJ { 321) ,DJ(22) ,DJ(23) ,DJ(24) ,DJ(25) ,DJ(26) , DJ (27) , 4DJ(28) ,DJ(29) ,DJ(30) ,DJ (31) ,DJ(32) ,'i)J (33) , EJ(34) , DJ { 535) ,DJ(36) ,DJ(37) ,DJ(38) , DJ (39) ,DJ (40) , DJ (4 1) ,DJ(42) , 6DJ (43) , DJ(44) ,DJ(45) , I LINE, SWTCH, LOG (1) ,LOG (2) , 7LOG (3) ,LOG (4) ,L0G (5) , LOG (6 ) , LOG (7) ,LOG (8 ) , LOG { 9) , 8LOG(10) ,LOG (11) - LOG (12) , LOG (13) , LOG (14) ,LOG (15) , 9LOG (16) ,LOG (17) ,LOG (18) ,LOG (19) ,LOG (20) ,LOG ( 21) , XLOG (22) ,LOG (23) ,LOG (24) ,LOG (25) ,LOG (26) ,LOG (27) ,LCG { 128) , LOG (29) ,LCG (30) ,LCG (31) ,LOG (3 2) , LOG (33) ,LOG ( 234) ,LOG(35) ,LOG ( 36) ,LOG (37) , LOG (38),LOG (39) ,LOG ( 34 0) , LOG (41) , LOG (4 2) , LOG (43) , LOG (4 4) ,TIMDJ, 4CHIPDJ,LCGNUM) ILINE=ILINE+1 IIL=ILINE*1000 TCL=. 1 ITREE=0 GRP=0 SWTCH=.TFUE. 10 ITREE=TTREE+1 J F (ITREE . GT. 44) GC TO 270 TCHIPS=0. CHPSKT-.FALSE. T I M £ = 0 . C C SELECT NEW LOG TO BE SUCKED C CALL SELECT ( BUTT , L EN , T DIA , ILOG, LOG N U.I) MSTAGE=LEN+1 C C SERO COEFFICIENTS C DO 20 1=1,HSTAGE EUCK(I)=SYM (1) POLICY (I) =0 LOSE (I) -0 F S ( I ) = 0 , c DO 20 J=1,24 C DO 20 K=1 ,6 20 COEF ( K , J , I) =0. C C D E T E R M I N E LOG COST C CST= ( T B I A * T B I A + RDIA (LEN + 1) * R D I A (LEN + 1) ) * L E N * . 1002727077* ( .30) FMAX=0. C C C DYNAMIC PROGRAMME C C c C S T A G E I S THE LOG L E N G T H PLUS ONE S T A R T I N G C AT T H E TOP END OF T H E L O G . C DO 60 S T A G E = 3 , M S T A G E , 2 L X 1 = S T A G E - 1 C C IPRD ARE THE ALLOWABLE BUCKING LENGTHS IN F E E T C L D O M - M I N O ( 2 4 , L X 1 ) C DO 50 I P R D = 2 , L D O M , 2 L X 2 = L X 1 - I P R D NN-LX2+1 C CALCULATE HEADRIG TIME. C C C DETERMINE THE RETURN TO THE L.P. SYSTEM AND C DETERMINE THE BEST OF FIVE POSSIBLE SAWING 71 C PATTERNS C CALL YLD (LX 1,LX 2, IPRD, VALD, ICANT, COF) HDUM = 0 . IF (IC ANT . EQ. 6) GO TO 30 HDTIM = 0.1333+FLOAT(IPRD)/47. 5 30 CONTINUE RETURN-VALU+FS(NN)+ H DTIM*TIMD J C C IS THIS STRATEGY BETTER THAN THE PREVIOUS C ST E ATEGY? C IF (RETURN . LE. FMAX) GO TO 5 0 C EO 40 J=2, IPRD, 2 C DO 40 N= 1,6 40 COEF (N,J,STAGE)=0. C POLICY(STAGE)=IPRD C COEFFICIENTS ARE THE COEFFICIENTS USED IN THE L. P. . C COEF(1,IPR D,STAGE)=CCF(1) COEF (ICANT, IPRD, STAGE) = COF(ICANT) IF(ICANT . LT. 6) LO AD (ST AGE) = 1 FM AX= RETURN FS(STAGE)=FMAX 50 CONTINUE C 60 CONTINUE C FM AX=Ffl AX + LOG (ILOG) DIFF=FMAX-CST IF (DIFF .LT. TOL) GO TO 10 C C C BACKWARD D.P. PASS C C NNSTAG=MST AG E+2 LENTOT=0 :> ILD=0 LfiA X=MSTAGE* 1 C DO 70 J=2,MSTAGE,2 IILEN=NNSTAG-J IF (POLICY (IILEN) .GT. 0.) GO TO 90 70 CONTINUE C WRITE (3,80) 80 FORMAT(4X,'ERROR') GO TO 10 90 NSTAGE=IILEN EUCK (LMAX-NSTAGE) =SYH ( 2) 10C NLEN=POLICY (NSTAGE) NN*NS~fcGE-KL_N IF ( L 0 ?. D (ii STAGE) .EQ. 0) GC T G 110 ILE=TLD+1 IENTOT = L?.NTGT+ N LEN 110 CONTINUE IF (NLEN .EQ. 0) GO TC 140 EUCK (LKAX-NN) =SY« (2) IF ( NSTAGE . EQ, MSTAGE) GO TC 130 C DO 120 1=1,6 COEE (I, NLEN , MST AGE) = COEF (I, NLEN , N STAG E) + 1COEF(I,NLEN,MSTAGE) 120 CONTINUE C 130 IF (NN . LT. 2) GO TO 140 NSTAGE-NN GC TO 100 140 CONTINUE C COMPLETE TREE IS NOT TO EE CHIPPEE! C IF(ILD .EQ. 0) GO TC 10 GR F= GRP+1 CALL BTD(TDIA,TOP(1),2,ND,'0') CALL BTDfLENfXLENJIJ^fND, 1 C ') C C CREATE THE REVISED EATA FILE. C IF (.NOT. SWTCH) GO TO 160 SWTCH=.FALSE. CALL BTD (ILINE, CHAR ( 1) ,3,ND,'0') WRITE (3,150) 150 FORMAT(•NAME',T15,•FEVDAT',/,*COL UMNS*,/,T3,* AFTER*) 16 0 CONTINUE C TIME=TIME+FLOAT (ILD) *0. 1333 + FIOAT (LENTOT)/47. 5 C DO 210 IPRD=2,24,2 IF (COEF (6, IPRD, MSTAGE) . GT. 0.) GO TO 200 C DO 190 ICANT=1,5 IF (COEF (ICANT,IPRD, MSTAGE) . EQ. 0.) "GC TO 190 CALL BTD(IPRD,PROD( 1) , 2,ND, • 0 1) WRITE (3,170) TOP, XLEN , CHAR, 1 DIM (ICANT) , PROD(1), PROD(2), COEF (IC ANT ,1PRD , MST AG E) 17C FORMAT(T5 , • L ' ,2(2A1) ,3A1,T15,•P2X',A2,«- 1,2A1,T25,F12. 16) KK= 5* ((I PRD-8) /2) t-ICANT IF(DJ(KK)) 190,190,180 180 EJ (KK) = BJ (KK) 190 CONTINUE C GO TO 210 200 CHPSKT-. TRUE. TCHIPS=TCHIPS+CCEF (6 , IPRD , MST AG E) 210 CONTINUE KBIT? (.3,220) TO?, XL EN, CHAP, T O P , X LE M 22 0 FORMAT (T5 , * L ' ,2 ( 2 A 1 ) , 3 A 1 , T 1 5 # , P L , , 2 ( 2 A 1 ) , T 2 9 R , 1 . ' ) WRITE (3,230) TOP, XLEN, CHAR, TIME C S T = - C S T 2 3 0 FORM AT (T 5, « L' , 2 ( 2 A 1) , 3 A 1, T 1 5 , « T I M E« , T 2 7 , F 8 . 4) WRITE ( 3 ,240) TOP, XLEN, CHAR, 1CST 2 4 0 FORMAT ( T 5 , , L ' f 2 ( 2 A 1 ) , 3 A 1 , T 1 5 , 'RETURN • ,T25,F10. 4) II = LEN+ 1 C CREATE BUCKING POLICY FOR REPORT WRITER. C WRITE (4'IIL,250) LEN, TDIA, EUTT, T O P , XLEN, CHAP, 1 (BUCK (J) ,J=1,II) 250 FORMAT (2X,I2,1X,I2, 1X,F3.0,2X, ,L',2(2A1),3A1,2X,7CA1) IIL=IIL+1 IF(CHPSWT) WRITE (3,260) TOP, XLEN, CHAR, TCHIPS 2 6 0 FORMAT(T5,'L',2 (2A1) ,3A1,T15,»WHLCHIP»,T25,F10.4) GC TO 1 0 27C CONTINUE WRITE (3,280) 280 FOEMAT('ENDATA*,/,* •) C C RETURN TO L. P. . C CALL PUTARG (DJ (1) ,DJ(2) ,DJ (3) ,DJ(4) ,DJ(5),DJ (6) ,DJ(7) , 1EJ(8) ,DJ(9) , DJ (10),DJ(11) ,DJ ( 1 2 ) ,D J (1 3) , D J ( 14) , 2DJ (15) ,DJ( 16) ,DJ(17) ,DJ ( 18) , DJ (1 9) ,DJ ( 2 0 ) ,DJ ( 321) ,DJ(22) ,DJ(23) ,DJ(24) ,DJ (25) ,DJ(26) , DJ(27) , 4EJ(28) ,DJ(29) ,DJ(30) ,DJ(31) -DJ(32) ,DJ(33) ,DJ(34) ,DJ( 535) ,DJ(36) ,DJ(37) ,DJ(38) ,DJ(39) ,DJ(40) , EJ(41) ,DJ (42), 6DJ(43) , DJ (44) , D J (45) ,ILINE,SWTCH, LOG (1) ,LOG (2) , 7LOG (3) ,LOG (4) ,LOG(5) , LOG (6) ,LOG (7) ,LOG (8) ,LCG (9) , 8LOG (10) ,LOG (11) ,LOG (12) ,LOG (13) , LCG( 14) ,L0G(15) , 9LOG (16) , LOG (17) ,LOG(18) ,LOG(19) ,LOG (20) ,LOG ( 21) , XLOG (22) ,LOG (23) ,LOG (24) ,LOG (25) ,LOG (26) ,LOG (27) ,LCG ( 128), LOG(29) ,LOG(30) ,LOG(31) ,LOG (32) ,LCG (33) ,LOG( 234) ,LOG (35) ,LOG( 36) ,LOG(37) ,LOG (38) , LOG (39) ,LOG ( 340) rLOG (41) ,LOG (42) ,LOG (43) , LOG (44) ,TIMDJ, 4CHIFDJ,LOGNUM) BETUBN END C C SUBBOUTINE SELECT(BUTT,LEN,TDIA,I LOG,LOGNUM) COMMON / BLK1/ YIELD, DJ, DIA, BDIA, CHIPDJ INTEGEB TDIA DIMENSION YIELD(20,5), D I A ( 3 9 ) , BDIA ( 9 9 ) , D J ( 4 5 ) C C DETEBMINE NEXT LOG C 10 LCGNUM=LOGNUM+1000 IF (LCG NUM .GT. 4 4 0 0 0 ) LCGNUM=1000 RE A E (2«LOGNUM,20) XLEN, T O P , BUTT, ILOG 20 FORMAT (3F3 . 0,2X ,12) D I A ( 1 ) = T O P P D I A (1 ) =D.I A (1) T A P E P = ( B U T T - T O P ) / X L E N I. E N •= X L E N T D I A = T O P C C A L C U L A T E D I A M E T E R S BY 1" D I A CLASSES AT C E A C H ' 2 • L O G L E N G T H . C DO 50 I L E N = 2 , L E N , 2 C I A (ILEN + 1) =TOP+ILEN*TAPER RDIA(ILEN+1)=DIA(ILEN+1) IDIA=IFIX ( D I A (ILEN + 1) ) D I FF= D I A (ILEN+1) - I D I A I F (DIFF . G T , 0.5) GO TO 30 D I A (ILEN + 1) = I D I A GO TO 4 0 30 ETA ( I L E N + 1) = I D I A + 1 , 40 CONTINUE 50 CONTINUE C RETURN END C c c SUBROUTINE YLD(LX1,LX2,IPRD,VALU,ICANT,COF) COMMON / BLK1/ YIELD, DJ, DIA, RDIA, CHIPDJ DIMENSION YIELD(20,5), DJ(45), DIA(99), RDIA(99), 1COF(6) CUBIC- (RDIA (LX1 + 1) *RDIA(LX1 + 1) +RDIA(LX2 + 1) *RDIA(LX2 + 1) 1)*IPBD* .002727077 C C RECOVERY 0.70 MBM/CUNIT C TBFBH=0.007*CUBIC IDIA=DIA (LX2 + 1) -6 C DO 10 J=1,5 10 COF (J) =0. C ICANT=6 COF (6)=CUBIC VALU=CHIPDJ*CUBIC IF(IPRD .LT. 8) GO TO 40 C CALCULATE * BEST' HEADRIG SAHING PATTERN IN TERMS CF THE C L.P. SYSTEM. C DO 30 NN=1 ,5 RET=THF EM* YI EL D (I DIA, NN) * D J ( 5* ( ( I P R D - 8) /2) + 1) + THFBM 1* (1 . - YIELD (IDIA,NN) ) * B J (5* ( (IPRD-8) /2) + NN) IF( RET .LT. VALU) GO TO 30 VALU= RET COF (1) =THFBM* YIELD { I C I A , UK) C O F (6)=0. 75 ICANT-NN IF (NK . EQ. 1) GO TO 30 C 20 K=2,NN 20 COF {K) =0 . C C DETERMINE MFBK YIEID FCR L.E.. C COF (N N)= TH F E M *(1.-YIELD(IEIA,NN)) 3 0 CONTINUE C 40 CONTINUE RETURN END C C c ELCCK DATA COMMON / BLK1/ YIELD, DJ, DIA, RDIA, CHIPDJ EI MENS ION YIELD (20, 5), DJ{45), DIA{99), RDIA (99) C C % SIDE LUMBER EY LOG DIAMETER C AND CANT THICKNESS (MAY BE MORE C T F AN 1 CANT PER DIAMETER CLASS) C ";" C C YIELDS BY DIAMETER (7-27) AND CANT SIZES C (4,6,8,10,AND 12 INCHES) C DATA YIELD/ 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 11 • f 1 • f 1 » y ^ * # ^ • # ^ * / ^ • * / ^ * # ^ * # • 5 0 ^  2.11, .05, .15, .23, .15, .20, .40, .40, .15, 3.23, .15, .20, .40, .40, .50, .40, .60, .60, 4.60, 1.0, 1.0, .50, .11, .05, .15, .23, .15, .20, .40, 5.40, .11, .05, .15, .23, .15, .20, .40, .40, .50, 1.0, 61.0, 1.0, 1.0, .50, .11, .05, .15, .23, .15, .20, 7.40, .40, .4 0, . 40, . 11 , .0 5, . 15, . 2 3, . 15, 81.0, 1.0, 1. 0, 1., 1.0, 1.0, .50, . 1 1, .05, 9. 15, .23, . 15, .20, .40, .40, .40, .40, .50, X.50, . 11/ END 76 APPENDIX II The source l i s t i n g of the MPSX proqram me. PROG RAM (' ND' ) * * JIM MCFHALEN * MAY, 1975 * INITIALZ MOV E (XP EN AM E, ' T EST 1') MOVE(XDATA,* TEST. 1«) MOVE (XOBJ, » RETURN' ) MOVE (XRHS, 'BVECT •) XDELTK= 1 MVADR {XDODELTM, LL6) MVADR{XDCNFS,OUT) CONVERT("SUMMARY','CHECK') SETUP('MAX') * \ r * CALL THE CONTROL SUBROUTINE. * SUB1 (PUN ,ITA ,ILINE , END) I T E R = I L I N E + I T A IF(PUN,BB) GOTO (SOL) BB M O V E ( X D A T A , •REVDAT *) I N S E R T * * O P T I M I Z E T H E L . P . * SOL O P T I M I Z E * * C E E C K T E E D E C O M P O S I T I O N COUNTER. * I F ( I L I N E . GT. I T E R , A A) SELECT ( 'ROW ,'RETURN*,NEW, ' ') I F (NEW .EQ. 0 . ,AER) E I F F = (NEW-OLE) /NEW MOVE(OLD,NEW) * * SAVE T H E CURRENT BASIS. * ARR SAVE (• NAME* ,'SAVIEASE') * * RETRIEVE THE "PRICES" FOR TEE SUE-PROBLEM. * SELECT (» PI»,» P2X0U-0 8',DJ1,» P2X0 6-08•,DJ2, 'P2X08-08 •,DJ3,•P2X10-08',DJ4, 'P2X1 2-0 8',DJ5, 'P2X0U-10', 'DJ6,1P2X06-10',DJ7,'P2XG8-10' DJ8, 'F2X10-10',DJ9,'P2X 12-10*,DJ1C,' ') 77 SELECT ( « PI • , •? 2 X 0 4 -1 2 ' , D J1 1, ' P2X06-12' , Cu12, «P2X08-12*,EJ13,'P2X10-12',IJ14,•P2X12-12», DJ15 , 'P2X04 - 14',DJ16, 'P2X06-14*,DJ17, 'P27.QS-1 4' , DJ1S,'P2X10-14' ,DJ19, ' ' ) SELECT('PI', «P2X12-14',DJ20,«P2X04-16' , DJ21 , « P2X06-16 ' ,DJ22, • P2X08-16•,DJ23,'F2X10-16»,CJ24,'F2X12-16', DJ25,'F2X0 4-18',DJ26,» P2X06-18•,DJ27,•P2X08-18•,DJ28, «P2X 10-18»,DJ29, 'P2Xl2-18',DJ30,'P2X04-20», DJ31 ,*P2X06-2C« ,DJ32,' ') SELECT (' PI' ,' P.2XC8-20' ,DJ 3 3, 'P 2X10-2 0' , D J3 4, * P2X12 -20 ' , DJ35,'P2X04-22',DJ36,'P2X06-22',DJ37,«P2X08-22•,EJ38, DJ39, 'P2X12-22',EJ4 0, « P2X04-2 4',DJ41,'P2X06-24',DJ4 2,* F2X08-24 ', DJ43, 'P2X 10-24', DJ 44, *P2X 12-24 *,DJ 45, ' KHLCHIP • ,CHIP,' • ) SELECT {'PI' ,'PL1168 ' ,L1, 'P11766',L2, 'PL 1664 »,L3, I FLO 962',L4,•PL0 860',L5,« PL 1960«,L6,•PL 1 458•,17, «PL 1256 *, L8,»PL1154',L9,•PL 1352*,L10,'PL 1250 ' ,L1 1,« PL1 048 »,L12, L12, 'PL0 946' ,L13,'PL1244* ,L14,'PL1242»,L15,» ') SELECT('PI*, 'PL 1 142',L 16,•PL 1042',L17,'PL1 940' ,L18, 'PL 1640',L19, *PL1540' ,L20,•PL 1340 • ,L21, 'PL1240',L22,'PL 1040', L23,»FL1238',L24,'PL1138',L25,•PL 1038',L26,«P10936',L27, •PL1234*,L28,*PL1534',L29,« ») SELECT {•PI* ,•PL 1634* ,L30,•PL16 32',L31,•PL 1132',L32, 'FI1230•,L33,» PL 13 28*,L34,•PL 1428',L35,'PL 1826*,L36,'PL13 26 •, L37, 'PL13 24*,L3 8,•PL1224 •,L39,•PL1122«,L40,'PL1220' ,L41, •PL2018*,L42,'PL1518*,L43,'PL 1116• ,L44,'TIME',TIMDJ, ' *) * * CALL BUCK.OPT * SUB2 (EJ1,DJ2,DJ3,DJ4,DJ5,DJ6,DJ7,DJ8,DJ9,DJ10, DJ11,DJ12,DJ13,DJ14,DJ15,DJ16,DJ17,DJ18,DJ19,DJ2 0,DJ21, DJ22,DJ23,DJ24,DJ25,DJ26,DJ27,DJ2 8,DJ29,DJ30,DJ31,DJ32, DJ33,DJ34,DJ35,DJ36,DJ37,DJ38,DJ39,DJ40,DJ41,DJ42,DJ43, DJ44,DJ45,ILINE,SHTCH,L1,L2,L3,L4,L5,L6,L7,L8,L9,L10, II 1,I12,L13,L14,L15,L16,L17,L18,L19,L20,L21,L22,L23,L24, L25,L26,L27,L28,L29,L30,L31,L32,L33,L34 ,L35,L36,L37,L38,L39, I40,I41,L42,L43,L44,TIMDJ,CHIP,LOGHUH) * * IF NO VECTOR FOUND - EXIT. * OTHERWISE - REVISE PROBLEM. * IF(SWTCH,AA) MOVE (XDATA, • REVDAT* ) MOVE (XPBNAME, *TEST 1«) MOVE(XOLDNAME,* TEST 1*) REVISE (• EILE* , ' F2' , • NOPRINT* ) SETUP (* MAX ') RESTORE ('NAME* ,'SflVEBASE* ) GOTO (SOL) * * EXIT! * AA SOLUTION PUNCHC VALU* , 'LIST') END=.TRUE. SUB1 (PUN , IT A , IL IN E, EN D) 73 G0T0(LL7) * - FEINT EASTS * LL6 EUNCU(»VALU',«LIST 1) CONTINUE CUT STATUS SOLUTION LL7 EXIT * * PRODUCT PRICES. * DJ1 DC (0. DJ2 DC (0. D J 3 DC (0. DJ4 DC (0. DJ5 DC (0. DJ6 DC (0. DO 7 EC (0. DJ 8 DC (0. DJ9 DC (0. DJ 10 DC (0. DJ11 EC (0. DJ12 DC (0. DJ13 DC (0. DJ 14 DC (0. DJ15 EC (0. DJ16 DC (0. DJ17 DC (0. DJ18 DC (0. DJ19 DC (0. DJ20 DC (0. DJ21 DC (0. DJ22 DC (0. DJ23 DC (0. DJ24 - DC (0. DJ25 DC (0. DJ26 DC (0. DJ27 DC (0. DJ28 DC (0. DJ29 DC (0. DJ30 DC (0. DJ31 DC (0. DJ32 DC (0. DJ33 DC (0. DJ34 DC (0. DJ35 DC (0. DJ36 DC (0. DJ37 DC (0. DJ38 DC (0. DJ39 EC (0. DJ40 DC (0. CJ41 DC (0. DJ42 DC (0. DJ43 EC (0. DJ44 DC (0. DJ45. CC(0.) * CONTROL VARIABLES. SKTCH DC (. FALSE.) ILINE DC (0) PUN DC {, FALSE.) END DC (. FALSE. ) ITER EC(0) IIA DC (Q) * COST OF LCG CONSTRAINTS. * L1 DC {0. L2 DC (0. L3 DC (0. L4 DC (0. L5 DC (0. L6 EC (0. L7 DC (0. L8 DC (0. L9 DC (0. n o EC (0. L11 DC (0. L12 DC (0. L13 DC (0. L14 DC (0. L15 DC (0. L16 DC (0. L17 DC (0. 118 DC (0. L19 DC (0. L20 DC (0. L21 DC (0. L22 DC (0. L23 DC (0. L24 DC (0. L25 DC (0. L26 DC (0. L27 DC to. L28 DC (0. L29 DC (0. L30 DC to. L31 DC (0. L32 DC (0. L33 DC [0. L3U DC (0. L35 DC (0. L36 DC (0. L37 DC (0. L38 DC (0. L39 DC (0. m o • DC [0. L41 DC (0. L<4 2 DC (0. LU3 DC (0. L4 U C C { 0 . ) * PROGRAMME VARIABLES. * TIKPJ DC(0.) NEW EC{0.) CLD DC(0.) TOL DC (.001) DI Ff r.C{0.) CRIP DC 10.) LCGNUM EC(0) PEND 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0075298/manifest

Comment

Related Items