Abstract

This paper addresses an identical parallel machine environment present in industry. In such an environment, no machine can execute more than one job at the same time. Each job is characterised by a release date that reflects the instant that the processing is able to start. There are no compatibility constraints between job and machine, so that each machine can perform any job. There are no precedence constraints or setup times between jobs. Whenever a job is scheduled after its due date, a penalty is incurred, reflecting the postponement. The scheduling of identical parallel machines has been proven to be important from both theoretical and practical points of view. In this paper, a metaheuristic based on GRASP with path relinking using a multi-threading approach is addressed. Computational experiments were conducted to compare metaheuristic solutions with lower bounds provided by a branch and bound algorithm. The proposed method is shown to be a competitive and effective solution strategy for production environments.

Key words: GRASP, path relinking, parallel machine, jobs, schedule, metaheuristic.