| Autor: |
崔晓龙(CUI Xiaolong), 何周力(HE Zhouli), 梅嘉杰(MEI Jiajie), 万龙(WAN Long) |
| Jazyk: |
čínština |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Zhejiang Daxue xuebao. Lixue ban, Vol 51, Iss 5, Pp 593-598 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
1008-9497 |
| DOI: |
10.3785/j.issn.1008-9497.2024.05.010 |
| Popis: |
we consider three two-machine flow-shop scheduling problems with periodic due dates, where each due date is assigned not to a specific job but to the processing order and the lengths of the intervals between two consecutive due dates are identical. The objectives are to minimize the maximum tardiness, the total tardiness and the total number of tardy jobs, respectively. In this paper, we show that all three problems are strongly NP-hard. Furthermore, our results also mean that if P≠NP, there is no pseudo polynomial-time algorithm and fully polynomial-time approximation scheme (FPTAS) to solve these problems.(考虑3个具有等间隔工期的双机流水作业调度问题，其中按照调度方案中工件的加工顺序给每个工期分配工件，且2个连续工期之间的间隔长度相同，目标分别为最小化最大延误、总延误和总误工工件数。证明了此三问题均为强NP-难的。此外，结果表明，如果P≠NP，那么这些问题没有伪多项式时间算法和完全多项式时间近似方案（FPTAS）。) |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
