Makespan Minimization on Injection Mould Shop Scheduling using Hybrid Dispatching Rules and Harmony Search

Amy L. Y. Tang, Kai-Ming Yu, and Peter Wan


Soft computing, optimization and scheduling, flexible flow shop, makespan


The paper addresses a flexible flow shop scheduling problem (FFSSP) with uniform parallel machines, non-anticipatory setup times, and stage skipping in an injection mould manufacturing shop. Hybrid Dispatching Rules and Harmony Search (HS) are proposed to solve this NP-hard problem with the objective to minimize the makespan. The Hybrid Dispatching Rules are combinations of Simple Dispatching Rules and Machine Assignment Rules. Three Simple Dispatching Rules are used to generate the Entry Point Sequence (EPS) of the jobs at the first stage while the jobs are queued according to FIFO rule at the remaining stages. Machine Assignment Rules are used for selecting the machine for processing in each stage. HS is employed to verify if there is any further improvement of the solution quality. Harmony Memory is initialized with either randomization or adoption of the solutions generated from the Hybrid Dispatching Rules. The experimental results indicate that ERT-ECT performs the best among the six Hybrid Dispatching Rules but HS is even better. In addition, the quality of the initial Harmony Memory has little impact on the final solution quality.

Important Links:

Go Back