標題: | 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 |