Customer order scheduling to minimize the number of late jobs
| dc.citation.epage | 948 | en_US |
| dc.citation.issue | 2 | en_US |
| dc.citation.spage | 944 | en_US |
| dc.citation.volume | 183 | en_US |
| dc.citation.woscount | 6 | |
| dc.contributor.author | Lin, B. M. T. | en_US |
| dc.contributor.author | Kononov, A. V. | en_US |
| dc.contributor.department | 資訊管理與財務金融系 註：原資管所+財金所 | zh_TW |
| dc.contributor.department | Department of Information Management and Finance | en_US |
| dc.date.accessioned | 2014-12-08T15:13:03Z | |
| dc.date.available | 2014-12-08T15:13:03Z | |
| dc.date.issued | 2007-12-01 | en_US |
| dc.description.abstract | In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date. (c) 2006 Elsevier B.V. All rights reserved. | en_US |
| dc.identifier.doi | 10.1016/j.ejor.2006.10.021 | en_US |
| dc.identifier.issn | 0377-2217 | en_US |
| dc.identifier.journal | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1016/j.ejor.2006.10.021 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/10072 | |
| dc.identifier.wosnumber | WOS:000247827500034 | |
| dc.language.iso | en_US | en_US |
| dc.subject | order scheduling | en_US |
| dc.subject | number of late jobs | en_US |
| dc.subject | approximability | en_US |
| dc.subject | approximation algorithm | en_US |
| dc.subject | multicover problem | en_US |
| dc.title | Customer order scheduling to minimize the number of late jobs | en_US |
| dc.type | Article | en_US |