A double relaxation grasp algorithm to solve the flowshop scheduling problem

Most production lines do not present an adequate way to plan their production, deciding for manual distribution and depending on the knowledge of their line or plant managers. This leads to a bad utilization of the resources, since conventional planning methods avoid considering complicated configurations. The kind of production line studied in this paper is flow shop scheduling (FSS hereafter) where tasks are independent and machines are homogeneous (they take almost the same time to perform a task), the machines are divided in families according to the function they have (FSS will force tasks to go through all the families) In this paper we present a GRASP metaheuristic algorithm to optimize lines as those defined above. The novelty is in the double relaxation criteria for both machines and tasks.