Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性)
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 tardines...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Zhejiang University Press
2024-09-01
|
| Series: | Zhejiang Daxue xuebao. Lixue ban |
| Subjects: | |
| Online Access: | https://doi.org/10.3785/j.issn.1008-9497.2024.05.010 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846149918778982400 |
|---|---|
| author | 崔晓龙(CUI Xiaolong) 何周力(HE Zhouli) 梅嘉杰(MEI Jiajie) 万龙(WAN Long) |
| author_facet | 崔晓龙(CUI Xiaolong) 何周力(HE Zhouli) 梅嘉杰(MEI Jiajie) 万龙(WAN Long) |
| author_sort | 崔晓龙(CUI Xiaolong) |
| collection | DOAJ |
| description | 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）。) |
| format | Article |
| id | doaj-art-d0409fce232045f1b5e9640d8c7437eb |
| institution | Kabale University |
| issn | 1008-9497 |
| language | zho |
| publishDate | 2024-09-01 |
| publisher | Zhejiang University Press |
| record_format | Article |
| series | Zhejiang Daxue xuebao. Lixue ban |
| spelling | doaj-art-d0409fce232045f1b5e9640d8c7437eb2024-11-29T09:37:32ZzhoZhejiang University PressZhejiang Daxue xuebao. Lixue ban1008-94972024-09-0151559359810.3785/j.issn.1008-9497.2024.05.010Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性)崔晓龙(CUI Xiaolong)0https://orcid.org/0000-0002-5785-7879何周力(HE Zhouli)1梅嘉杰(MEI Jiajie)2万龙(WAN Long)3https://orcid.org/0000-0001-9770-532XSchool of Information Management， Jiangxi University of Finance and Economics， Nanchang 330013， China(江西财经大学 信息管理学院，江西 南昌 330013)School of Information Management， Jiangxi University of Finance and Economics， Nanchang 330013， China(江西财经大学 信息管理学院，江西 南昌 330013)School of Information Management， Jiangxi University of Finance and Economics， Nanchang 330013， China(江西财经大学 信息管理学院，江西 南昌 330013)School of Information Management， Jiangxi University of Finance and Economics， Nanchang 330013， China(江西财经大学 信息管理学院，江西 南昌 330013)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）。)https://doi.org/10.3785/j.issn.1008-9497.2024.05.010two-machine flow-shop scheduling(2台机器调度)periodic due dates(等间隔工期)tardiness(延误)np-hardness(np-难) |
| spellingShingle | 崔晓龙(CUI Xiaolong) 何周力(HE Zhouli) 梅嘉杰(MEI Jiajie) 万龙(WAN Long) Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性) Zhejiang Daxue xuebao. Lixue ban two-machine flow-shop scheduling(2台机器调度) periodic due dates(等间隔工期) tardiness(延误) np-hardness(np-难) |
| title | Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性) |
| title_full | Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性) |
| title_fullStr | Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性) |
| title_full_unstemmed | Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性) |
| title_short | Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性) |
| title_sort | strong np hardness of two machine flow shop scheduling with periodic due dates 具有等间隔工期的2台机器流水作业调度问题的强np难性 |
| topic | two-machine flow-shop scheduling(2台机器调度) periodic due dates(等间隔工期) tardiness(延误) np-hardness(np-难) |
| url | https://doi.org/10.3785/j.issn.1008-9497.2024.05.010 |
| work_keys_str_mv | AT cuīxiǎolóngcuixiaolong strongnphardnessoftwomachineflowshopschedulingwithperiodicduedatesjùyǒuděngjiāngégōngqīde2táijīqìliúshuǐzuòyèdiàodùwèntídeqiángnpnánxìng AT hézhōulìhezhouli strongnphardnessoftwomachineflowshopschedulingwithperiodicduedatesjùyǒuděngjiāngégōngqīde2táijīqìliúshuǐzuòyèdiàodùwèntídeqiángnpnánxìng AT méijiājiémeijiajie strongnphardnessoftwomachineflowshopschedulingwithperiodicduedatesjùyǒuděngjiāngégōngqīde2táijīqìliúshuǐzuòyèdiàodùwèntídeqiángnpnánxìng AT wànlóngwanlong strongnphardnessoftwomachineflowshopschedulingwithperiodicduedatesjùyǒuděngjiāngégōngqīde2táijīqìliúshuǐzuòyèdiàodùwèntídeqiángnpnánxìng |