A Heuristic algorithm for the multi-item capacitated lotsizing problem

Abstract

ÖZET Bu çalışmada tek aşamalı çok ûrünlü zamanla değişen kapasite kısıtlı kafile büyüklüğü belirlemesi ve çizelgelemesi problemi incelenmiştir. Talebin belirli ve bağımsız olduğu kabul edilmiştir. Hazırlık zamanları ve hazırlık maliyetleri model gösterimine birlikte dahil edilmişlerdir. Problemin Lagrange metodu ile gevşetilmiş şekli için bir sezgisel algoritma geliştirilmiştir, önerilen metodda Lagrange çarpanları sabgradyan en iyilemesi ile güncelleştirilmektedir. Algoritma iki safha içermektedir. İlk safhada problem kapasite kısıtları göz önüne alınmaksızın çözülür, ikinci safhada üretim çizelgeleri mevcut kapasitelere göre düzeltilir. Test edilen problemler, algoritmanın en iyiye yakın çözümler verdiğini ve pratikte oldukça verimli bir şekilde kullanılabileceğini göstermektedir. Anahtar sözcükler: Kafile büyüklüğü belirlemesi, üretim çizelgelemesi, Lagrange gevşetmesi, sabgradyan en iyilemesi.

IV ABSTRACT In this study single stage, multi-item capacitated lotsizing and scheduling problem (CLSP) with time varying capacity constraints, was examined. Demand was assumed to be deterministic and independent. Both setup times and setup costs were included in the model formulation. A heuristic algorithm was developed for the solution of Lagrangean relaxed form of the problem. In the proposed methodology Lagrange multipliers are updated by subgradient optimization. The approach includes two phases. In phase I problem is solved without considering capacity constraints, and in phase II production schedules are smoothed according to the available capacities. Problems tested indicate that the algorithm gives near optimal solutions and can be used quite effectively in practice. Keywords: Lotsizing, production scheduling, Lagrangean relaxation, subgradient optimization.