標題: Complexity results for single-machine scheduling with positional learning effects
作者: Lin, B. M. T.
資訊管理與財務金融系 註:原資管所+財金所
Department of Information Management and Finance
關鍵字: single-machine scheduling;learning effect;late job;NP-hardness
公開日期: 1-Aug-2007
摘要: This note presents complexity results for a single-machine scheduling problem of minimizing the number of late jobs. In the studied problem, the processing times of the jobs are defined by positional learning effects. A recent paper proposed a polynomial time algorithm for the case with a common due date and conjectured the general problem to be NP-hard. We confirm that the general problem is strongly NP-hard and show that the studied problem remains NP-hard even if there are only two different due-date values.
URI: http://dx.doi.org/10.1057/palgrave.jors.2602227
http://hdl.handle.net/11536/10464
ISSN: 0160-5682
DOI: 10.1057/palgrave.jors.2602227
期刊: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
Volume: 58
Issue: 8
起始頁: 1099
結束頁: 1102
Appears in Collections:Articles