This chapter presents an application of a fuzzy programming approach for multiple objectives to the aggregate production planning (APP). The APP parameter levels have been applied via a case study from the SMEs company in Thailand. The proposed model attempts to minimise total production cost and minimise the subcontracting units. Conventional harmony search algorithm (HSA) with its hybridisations of the novel global best harmony search (NGHSA) and the variable neighbourhood search of the HSA (VHSA) including the hunting search (HuS) element on the pitch adjustment (HuSHSA). Based on the experimental results, it can be concluded that each algorithm is suitable for different types of situations. However, for all situations VHSA and NGHSA can obtain good solutions. Furthermore, the proposed VHSA is more effective than other approaches in terms of superiority of solution and required CPU time. © 2012 Springer Science+Business Media, LLC.