| Scheduling a set of jobs on unrelated parallel machines is very common in practice. Unfortunately, for most performance measures, unrelated parallel machine scheduling problems are NP-Hard. In order to generate good solutions in a reasonable computation time, heuristics need to be developed. In this research, we consider data generation and heuristics for unrelated parallel machine scheduling problems.;First we consider the problem of generating processing times for parallel machine scheduling problem instances. We present processing time generation schemes that consider different levels and combinations of machine correlation and job correlation. Also, metrics to evaluate the amount of machine relatedness and job uniformity for the processing times of a given problem instance are presented. Computational results indicate that the proposed generation schemes have desirable principles and properties.;Second, several heuristics and a Genetic Algorithm (GA) for scheduling unrelated parallel machines problems to minimize the makespan, total weighted completion time, and total weighted tardiness when each objective is considered individually are proposed. Computational results show that the proposed heuristics outperform the best existing heuristics from the literature for these objectives.;Third, two bi-criteria heuristics and a multi-objective Genetic Algorithm (GA) is proposed to find Pareto optimal (or near Pareto optimal) solutions to the unrelated parallel machines scheduling problem that minimizes makespan, total weighted completion time, and total weighted tardiness, simultaneously. The computational results show that the heuristic approaches provide reasonable solution qualities while also being computationally efficient. Also, the proposed GA outperforms other algorithms in terms of the number of (near) Pareto optimal solution and the Integrated Preference Functional (IPF) value. |
