On-line Parallel Machine Scheduling With Special Jobs To Minimize The Makespan

In this paper, we investigate parallel machine on-line scheduling problem with special jobs to minimize the makespan. Using the 3-field notation of Graham et al. [12], the problem is denoted as Pm|on-line-list; special jobs(M₁)|C_max, where M₁ represents that the special jobs must be assigned to the first machine. When the job list has no special jobs, the problem degenerates as the classical parallel machine on-line scheduling problem Pm | on-line-list|C_max.On-line, in this paper means on-line-list: the job comes over list and we get the jobs one by one. Once a job is released, we must immediately decide on which machine the job is processed. The jobs are not known a priori: job J_j becomes known only when job J_j-1 has already been scheduled. Once a job is assigned to the machine, we are not allowed to move the job to another machine.In the scheduling problem under consideration, we have two kinds of jobs: normal jobs and special jobs. The normal jobs can be processed on any one of the parellel machines, while the special jobs must be processed on their own specified machine. In this paper, all the special jobs in each instance are specified to be processed on machine M₁.In production practice, special jobs widely exist. They have some special properties so that they must be processed on their own specified machines. In these cases, the existance of special jobs will make the problem becoming much more complex.The main results of this paper are as follows:(1) The case of two machines: P2|on-line-list; special jobs(M₁)|C_max. We show that there is no on-line algorithm with competitive ratio less than 5/3, and present a best possible on-line algorithm.(2) The case of three machines: P3|on-line-list; special jobs(M₁)|C_max. We show that there is no on-line algorithm with competitive ratio less than 1.686, and present an on-line algorithm which has the competitive ratio of at most 1.857.(3) The case of m (m≥4) machines: Pm|on-line-list; special jobs(M₁)|C_max. The lower bound in this case is at least the lower bound of Pm|on-line-list|C_max, and present an on-line algorithm which has the competitive ratio of at most...