Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs
檔案
本條目沒有附加檔案。
日期
2019-08-01
類型
期刊名稱
JOURNAL OF SCHEDULING
卷期與頁次
第 22 卷第 4 期,頁 413–431
ISSN
1094-6136
語言
英文
摘要
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.
關鍵詞
Parallel-machine schedulingNumber of tardy jobsPreemptionMixed integer programHeuristic performance analysis所屬典藏
期刊論文引用此條目
Hung, H.-C., Lin, B. M. T., Posner, M. E., & Wei, J.-M. (2019). Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs. JOURNAL OF SCHEDULING, 22(4), 413–431. https://doi.org/10.1007/s10951-018-0584-y
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/152186