This study presents a multiobjective scheduling model on parallel machines (MOSP). Compared with other scheduling problems on parallel machines, the MOSP is distinct for the following characteristics: (1) parallel machines are nonidentical, (2) the type of jobs processed on each machine can be restricted, and (3) the multiobjective scheduling problem includes minimizing the maximum completion time among all the machines (makespan) and minimizing the total earliness/tardiness penalty of all the jobs. To solve the MOSP, a new parallel genetic algorithm (PIGA) based on the vector group encoding method and the immune method is proposed. For PIGA, its three distinct characteristics are as follows: Firstly, individuals are represented by a vector group, which can effectively reflect the virtual scheduling policy. Secondly, an immune operator is adopted and studied in order to guarantee diversity of the population. Finally, a local search algorithm is applied to improve the quality of the population. Numerical results show that it is efficient, can better overcome drawbacks of the general genetic algorithm, and has better parallelism.