Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem
- PDF / 201,578 Bytes
- 16 Pages / 595 x 842 pts (A4) Page_size
- 7 Downloads / 163 Views
#1999 Operational Research Society Ltd. All rights reserved. 0160-5682/99 $12.00 http://www.stockton-press.co.uk/jor
Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem È zdamar1 and G BarbarosogÆlu2 LO 1
Istanbul KuÈltuÈr University, and 2BogazicËi University, Istanbul, Turkey
The multi-stage capacitated lot sizing and loading problem (MCLSLP) deals with the issue of determining the lot sizes of product items in serially-arranged manufacturing stages and loading them on parallel facilities in each stage to satisfy dynamic demand over a given planning horizon. It is assumed that regular time capacity decisions have already been made in the tactical level and allocated to the stages, but it is still an important decision problem whether to augment regular time capacity by overtime capacity. Each item may be processed on a technologically feasible subset of existing facilities with different process and setup times on each facility. Since the solution of the MCLSLP requires the design of a powerful algorithm, simulated annealing (SA) and genetic algorithms (GA) are integrated to enhance their individual performances. Furthermore, these global optimisation methods are incorporated into a Lagrangean relaxation scheme, hence creating a hybrid solution methodology. Numerical results obtained using these methods con®rm the mutual bene®ts of integrating different solution techniques. Keywords: Heuristics; simulated annealing; genetic algorithms; Lagrangean relaxation; multi-stage lot sizing
Introduction The multi-stage capacitated lot sizing and loading problem (MCLSLP) addresses the issue of determining the production lot sizes of various items appearing in consecutive production stages over a given planning horizon. The production environment considered in this study can be best described as a ¯ow-type process manufacturing such that some processing is done on the material in each stage as it proceeds through serially-arranged stages and that the item has no distinct identity as a ®nished product until it leaves the very last stage. Therefore the same product index is preserved for an item in each stage although the material undergoes transformation as it moves downstream. Examples of this type of manufacturing include steel mills, chemicals, plastics, pharmaceuticals, ceramics, glass plants and re®neries. Although it can be argued that there usually exists one bottleneck which is stable over time in such plants, when there are parallel facilities in each stage so that an item may be produced on more than one facility, and especially if the associated processing times exhibit considerable variation, the loading scheme may lead to different capacity utilisation rates in each stage over time. Therefore, one stage which is bottleneck in a certain time period may not be bottleneck in another time period. This implies that bottlenecks are not necessarily stable and do change dynamically over time in case of parallel facilities. Furthermore, Correspondence: Dr. G BarbarosogÆlu BogazicËi Universi
Data Loading...
