標題: Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs
作者: Hung, Hui-Chih
Lin, Bertrand M. T.
Posner, Marc E.
Wei, Jun-Min
工業工程與管理學系
資訊管理與財務金融系 註:原資管所+財金所
Department of Industrial Engineering and Management
Department of Information Management and Finance
關鍵字: Parallel-machine scheduling;Number of tardy jobs;Preemption;Mixed integer program;Heuristic performance analysis
公開日期: 1-Aug-2019
摘要: 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.
URI: http://dx.doi.org/10.1007/s10951-018-0584-y
http://hdl.handle.net/11536/152186
ISSN: 1094-6136
DOI: 10.1007/s10951-018-0584-y
期刊: JOURNAL OF SCHEDULING
Volume: 22
Issue: 4
起始頁: 413
結束頁: 431
Appears in Collections:Articles