On the economic lot scheduling problem

Abstract

The Economic Lot Scheduling Problem (ELSP), that schedules production of multiple products on a single machine under capacity constraints, is one of the classic problems in operations research. The Extended Basic Period (EBP) and Power-of-Two (PoT) policy is used and several algorithms are developed in this thesis. The problem is formulated as a nonlinear integer programming problem and a parametric search algorithm is developed to find the optimal solution. After which, a faster heuristic and a genetic algorithm based on insights drawn from the algorithm are developed. The Multiple-machine ELSP (MELSP) which schedules many products on identical multiple machines is also discussed. A genetic algorithm under the Common Cycle (CC) policy and a genetic algorithm under the EBP and PoT policy are developed and shown better than previous heuristic methods.