Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs

Hui-Chih Hung, Bertrand M.T. Lin*, Marc E. Posner, Jun Min Wei

*此作品的通信作者

研究成果: Article同行評審

12 引文 斯高帕斯(Scopus)

摘要

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

指紋

深入研究「Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs」主題。共同形成了獨特的指紋。

引用此