GRASP Algorithm Applied to the Problem of Job Sequencing with Position-Dependent Decay Rate

Job sequencing in parallel production lines is part of the daily problem of medium and large companies, considering scarce resources and high demand. This paper addresses a job sequencing problem on parallel workers with position-dependent deterioration of times, minimizing the maximum tardiness with respect to job due dates. This problem is characterized as being NPHard due to the high computational complexity to find optimal solutions through exact methods. Therefore, a simple and efficient GRASP heuristic is proposed. The objective is to compare the performance of the GRASP heuristic in relation to a VND heuristic from the literature and the integer linear programming mathematical model of the problem