摘要
This paper investigates the classical preemptive parallel-machine scheduling problem of maximizing number of on-time jobs. While the problem is known to be NP-hard, no theoretical analysis of approximation algorithms exists in the literature. As part of the analysis, a new non-standard mixed integer formulation is developed. We propose heuristics based on different design strategies. These heuristics have asymptotically tight relative errors of 1/2. Experimental tests evaluate the computational performance of the procedures.
原文 | American English |
---|---|
頁(從 - 到) | 413-431 |
頁數 | 19 |
期刊 | Journal of Scheduling |
卷 | 22 |
發行號 | 4 |
DOIs | |
出版狀態 | Published - 15 8月 2019 |