A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines

A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines

0.00 Avg rating0 Votes
Article ID: iaor20083586
Country: Netherlands
Volume: 175
Issue: 2
Start Page Number: 1070
End Page Number: 1083
Publication Date: Dec 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: scheduling, heuristics, lagrange multipliers
Abstract:

This paper addresses the capacitated lot-sizing problem involving the production of multiple items on unrelated parallel machines. A production plan should be determined in order to meet the forecast demand for the items, without exceeding the capacity of the machines and minimize the sum of production, setup and inventory costs. A heuristic based on the Lagrangian relaxation of the capacity constraints and subgradient optimization is proposed. Initially, the heuristic is tested on instances of the single machine problem and results are compared with heuristics from the literature. For parallel machines and small problems the heuristic performance is tested against optimal solutions, and for larger problems it is compared with the lower bound provided by the Lagrangian relaxation.

Reviews

Required fields are marked *. Your email address will not be published.