New utilization criteria for . . .

In the classical scheduling problems, it has been assumed that complete knowledge of the problem was available when it was to be solved. However, scheduling problems in the real world face the possibility of the lack of the knowledge. Uncertainties fre-quently encountered in scheduling environments include the appearance of new jobs and unknown processing times. In this work, we take into account these realistic is-sues. This thesis deals with the problem of non-preemptive scheduling independent jobs on m identical parallel machines. In our online model, the jobs are submitted over time non-clairvoyantly. Therefore, the processing times of the jobs are unknown until they complete. Further, we assume that the ratio of weight to processing time is equal for all jobs, that is, all jobs have the same priorities. The jobs are assigned to the machines in a nondelay fashion. Our main scheduling objective is to maximize the utilization of the system. We show that the commonly used makespan criterion usually cannot reflect th