Bicriteria scheduling problem for unrelated parallel machines

In this paper scheduling of n jobs, all requiring a single stage of processing, on m unrelated parallel machines is considered. No preemption of jobs is allowed. There are two scheduling objectives, namely to minimize the makespan and to minimize the maximum tardiness. An algorithm based on tabu search is proposed for the above problem. Computational results are reported with data generated using various combinations of process time and due dates. Comparison is also made with a heuristic proposed earlier. The results show that the proposed algorithm gives better results both in terms of the quality of solution and execution time.