Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups

We consider the problem of scheduling N jobs on M unrelated parallel machines to minimize maximum tardiness. Each job has a due date and requires a single stage of processing. A setup for dies is incurred if the type of the job scheduled is different from the previous one on that machine. For each die type, the number of dies is restricted. Because of the mechanical structure of the machines and the fitness of dies to each machine, the processing time depends on both the job and the machine. In this paper, an efficient heuristic based on guided search, record-to-record travel, and tabu lists is presented to minimize maximum tardiness. Computational characteristics of the proposed heuristic are evaluated through extensive experiments, which show that the proposed heuristic outperforms a simulated annealing method tested and is able to prescribe the optimal solutions for problems in small scales.