A heuristic to minimize total terdiness on parallel machines: an aggregate planning approach

Abstract

Unrelated parallel machine total tardiness problem is investigated in this study. Job-splitting property, eligibility constraints and family setup structure are assumed. A previous study focused on the exact problem does not exist. We proposed a four phased heuristic in order to cope with the problem. Phase - I aggregates the jobs given two control parameters and generates aggregate jobs. Phase - II generates a time structure based on the due dates of the aggregate jobs fed from Phase - I. After that, Phase - II constructs an aggregate planning model and solves it iteratively. Phase - III generates a feasible schedule given the output of the aggregate planning model. At the end, Phase - IV, the tuning phase, tunes the control parameters and runs previous phases for a number of times. 480 problem instances are generated in order to test the proposed heuristic. On the other hand, some of the problem instances are also solved with CPLEX. The results show that the proposed heuristic gives better result than what CPLEX found within the 24 hour CPU time limit. We conclude that the proposed heuristic performs well in a reasonable amount of CPU time.