GRASP with path relinking for a multiple objective sequencing problem for a mixed-model assembly line

Abstract

This research presents a new application of greedy randomised adaptive search procedure (GRASP) to address a production sequencing problem for mixed-model assembly line in a just-in-time (JIT) production system in two different cases. In the former case, small size sequencing problems are considered and two objectives are presented; minimisation of setups and optimisation of stability of material usage rates. These two objectives are inversely correlated with each other, so simultaneous optimisation of both is challenging. This type of problem is NP-hard. The GRASP, with path relinking, searches for efficient frontier where simultaneous optimisation of number of setups and usage rates is desired. Several test problems are solved via GRASP and its performance is compared to solutions obtained via complete enumeration and simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) approaches from the literature. Experimental results reveal that the GRASP with path relinking provides near-optimal solutions in terms of the two objectives and its ‘average inferiority%’ and ‘average percentile’ performances are superior to that of other heuristics. In the latter case, the goal is to explore varying the emphasis of these two conflicting objectives. Larger sequencing problems are considered and solved via GRASP with path relinking. Its objective function values are compared to the solutions obtained via a SA approach from the literature. Experimental results show that GRASP also provides good performance on large size problems and its percentage improvement is better than that of SA. Overall results also show, however, that the GRASP performs poorly with regard to CPU time.

Keywords:

• multiple objective decision making
• mixed-model sequencing
• mixed-model assembly line
• heuristics
• greedy randomised adaptive search procedure
• optimisation