A Genetic Algorithm for Solving Single Level Lot–Sizing Problems

Abstract

Masalah pensaizan lot satu aras timbul apabila suatu syarikat pengeluar ingin menjanakan perancangan pengeluaran terperinci bagi produk berpandukan suatu perancangan agregat. Walaupun masalah ini telah dikaji dengan meluas, hanya pendekatan pengaturcaraan dinamik dapat menjamin penyelesaian yang minimum secara global. Maka heuristik-heuristik stokastik yang mampu melepasi minimum tempatan adalah diperlukan. Kajian ini mencadangkan kaedah algoritma genetik untuk menyelesaikan masalah-masalah pensaizan lot satu aras, serta membincangkan beberapa contoh aplikasi kaedah tersebut. Dalam pelaksanaan kaedah ini, heuristik penjanaan populasi pensaizan lot yang dapat menjanakan populasi awal digunakan untuk menyediakan kromosom. Kromosom ini digunakan sebagai input untuk algoritma genetik dengan operator-operator yang khusus bagi masalah pensaizan lot. Gabungan heuristik penjanaan populasi dengan algoritma genetik menghasilkan penumpuan yang lebih pantas dalam proses mendapatkan skim pensaizan lot yang optimum disebabkan oleh ketersauran populasi awal yang digunakan. Kata kunci: ALgorithm Genetik; Pensaizan lot The single level lot-sizing problem arises whenever a manufacturing company wishes to translate an aggregate plan for production of an end item into a detailed planning of its production. Although the cost driven problem is widely studied in the literature, only laborious dynamic programming approaches are known to guarantee global minimum. Thus, stochastically-based heuristics that have the mechanism to escape from local minimum are needed. In this paper a genetic algorithm for solving single level lot-sizing problems is proposed and the results of applying the algorithm to example problems are discussed. In our implementation, a lot-sizing population-generating heuristic is used to feed chromosomes to a genetic algorithm with operators specially designed for lot-sizing problems. The combination of the population-generating heuristic with genetic algorithm results in a faster convergence in finding the optimal lot-sizing scheme due to the guaranteed feasibility of the initial population. Key words: Genetic Algorithm; Lot-sizing