Abstract: Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51) study the following problem: there are n orders each of which requests various quantities of the different product types. All the orders are available for processing at time t=0, and preemption is allowed. Order i has a weight \omega_{i} and its completion time is the time when its last requested product type is completed. The goal is to find a preemptive schedule such that the total weighted completion time \sum\limits_{i=1}^n\omega_{i}C_{i} is minimized. They show that this problem is NP-hard and propose a heuristic with worst-case ratio analysis. When reading the proof of Theorem 2 in this paper, we find that some statements are not correct. In this paper, we show that although the proof of Theorem 2 is not valid, the conclusion is still right. Furthermore, we propose an improved approximation algorithm for a special case.

Key words: scheduling, approximation algorithm, NP-hard