Preemptive multiprocessor order scheduling to minimize total weighted flowtime |
| |
Authors: | Joseph Y-T Leung CY Lee CW Ng GH Young |
| |
Institution: | 1. Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA;2. Department of Industrial Engineering and Engineering Management, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong;3. Department of Computer Science, Morehouse College, Atlanta, GA 30314, USA;4. Department of Computer Science, California State Polytechnic University, Pomona, CA 91768, USA |
| |
Abstract: | Consider m identical machines in parallel, each of which can produce k different product types. There is no setup cost when the machines switch from producing one product type to another. There are n orders each of which requests various quantities of the different product types. All orders are available for processing at time t = 0, and preemption is allowed. Order i has a weight wi and its completion time is the time when its last requested product type finishes. Our goal is to find a preemptive schedule such that the total weighted completion time ∑wiCi is minimized. We show that this problem is NP-hard even when all jobs have identical weights and there are only two machines. Motivated by the computational complexity of the problem, we propose a simple heuristic and show that it obeys a worst-case bound of 2 − 1/m. Finally, empirical studies show that our heuristic performs very well when compared with a lower bound of the optimal cost. |
| |
Keywords: | Order scheduling Total weighted completion time Flexible machines NP-hard Heuristics |
本文献已被 ScienceDirect 等数据库收录! |
|