A Discrete Harmony Search Algorithm for the Economic Lot Scheduling Problem with Power of Two Policy

Abstract

In this paper we present a problem specific discrete harmony search (DHS) algorithms to solve the economic lot scheduling problem (ELSP) under the extended basic period (EBP) approach and power-of-two (PoT) policy. In particular DHS algorithms generate a cyclic production schedule consisting of n items to be produced on a single machine where the production cycle of each item is an integer multiple of a fundamental cycle. All the integer multipliers take the form of PoT which restricts the search space but provides good solution qualities. Under the EBP approach feasibility is guaranteed with a constraint checking whether or not the items assigned in each period can be produced within the length of the period. For this restricted problem which is still NP-hard the proposed DHS algorithms employ a multi-chromosome solution representation to encode power-of-two multipliers and the production positions separately. Both feasible and infeasible solutions are maintained in the population through the use of some sophisticated constraint handling methods. A variable neighborhood search (VNS) algorithm is also hybridized with DHS algorithms to further enhance the solution quality. The experimental results show that the proposed algorithms are very competitive to the best performing algorithms from the existing literature under the EBP and PoT policy