Algorithmic Analysis of the Unrelated Parallel Machines Scheduling Problem to Minimize Mean Weighted Flowtime

摘要

This paper provides algorithmic analysis for the scheduling of nonpreemptive independent jobs on unrelated parallel machines to minimize the mean weighted flowtime from two competing aspects: Constructive and improvement algorithms. A general heuristic approach for developing the constructive algorithms is proposed. Based on this, two types of constructive algorithms are developed: ratio-of-flowtime-to-weight based algorithms and product-of-flowtime-and-weight based algorithms. An improvement procedure that uses the combined reassigning and pairwise interchanging to improve the initial solution is also presented. The performances of the algorithms are evaluated via statistical optimization technique and simulation studies. The experimental results show that the improvement procedure can always yield very elaborate near optimum solutions at small computational expense. For constructive algorithms, one product-based algorithm outperforms the others. The results also indicate that the product-based approach proposed in this paper is a new and promising way for obtaining good constructive algorithms.