On-line Scheduling of Two Uniform Machines to Minimize Total Completion Times(Abstract)

摘要

We study on-line scheduling problems on two uniform machines. We suppose machine M1 has a speed of 1 and M2 has a speed of s with no less than 1. Each machine can process only one job at a time. Jobs are arriving over time. Each job J_j has a non-negative release time r_j, processing time p_j and weight W_j. We learn these job data only after its release time r_j. The number of jobs is not known in advance, and no information is known about any future jobs. We consider the non-preemptive machine environments with the objective to minimize the total completion times and the preemptive machine environments with the objective to minimize the total weighted completion times. In the non-preemptive setting, once a job is started on a machine, it must be processed on the same machine without any interruption until its completion. In contrast, in the preemptive setting, the processing of a job may be suspended and resumed later on any machine at no extra cost. For the non- preemptive version with the objective to minimize the total completion times, we apply the idea of a single machine preemptive relaxation. Given an instance J for non-preemptive scheduling on two uniform machines, we define a single machine preemptive relaxation instance I~1 of 1|r_j,pmtn| ΣC_j as follows: The single machine has a speed of 1+s. I~1 has the same set of jobs as those of I and the job J_j in I~1 has the same release time and processing time as in J. Based on single machine preemptive relaxation, we present the Algorithm FCFS and this algorithm is 2.76-competitive. In the preemptive version with the objective to minimize the total weighted completion times, we give an on-line Algorithm WSPT by applying WSPT and SRPT rules. We show that this algorithm is 2-competitive and this bound is tight.