单选题：Scheduling Job Problem
**Scheduling Job Problem**: There are $n$ jobs and $m$ identical machines (running in parallel) to which each job may be assigned. Each job $j =1, \cdots, n$ must be processed on one of these machines for $t_j$ time units without interruption. Each machine can process at most one job at a time. The aim is to complete all jobs as soon as possible; that is, if job $j$ completes at a time $C_j$ (the schedule starts at time $0$), then we wish to minimize $C_{max} = max_{j=1,\cdots, n}C_j$. The length of an optimal schedule is denoted as $OPT(C_{max})$.
**Local Search Algorithm**: Start with any schedule; consider the job $l$ that finishes last; check whether or not there exists a machine to which it can be reassigned that would cause this job to finish earlier. If so, transfer job $l$ to this other machine. The local search algorithm repeats this procedure until the last job to complete cannot be transferred. An illustration of this local move is shown in following figure.
Which of the following statement is false?
A.$OPT(C_{max}) \geq \sum_{j=1}^{n} t_j / m$
B.When transfering a job, if we always reassign that job to the machine that is currently finishing earliest, then no job is transferred twice.
C.Upon the termination of the algorithm, the algorithm may return a schedule that has length at least $2OPT(C_{max})$
D.Suppose that we first order the jobs in a list arbitrarily, then consequently assign each job to the machine that is currently of earliest completion time, the schedule obtained cannont be improved by the local search procedure.
答案：C
**Local Search Algorithm**: Start with any schedule; consider the job $l$ that finishes last; check whether or not there exists a machine to which it can be reassigned that would cause this job to finish earlier. If so, transfer job $l$ to this other machine. The local search algorithm repeats this procedure until the last job to complete cannot be transferred. An illustration of this local move is shown in following figure.
Which of the following statement is false?
A.$OPT(C_{max}) \geq \sum_{j=1}^{n} t_j / m$
B.When transfering a job, if we always reassign that job to the machine that is currently finishing earliest, then no job is transferred twice.
C.Upon the termination of the algorithm, the algorithm may return a schedule that has length at least $2OPT(C_{max})$
D.Suppose that we first order the jobs in a list arbitrarily, then consequently assign each job to the machine that is currently of earliest completion time, the schedule obtained cannont be improved by the local search procedure.
答案：C