| 工件具有子工件工期的排序问题 |
| |
| 引用本文： | 仲维亚,杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.006 |
| |
| 作者姓名： | 仲维亚 杨若瑶 |
| |
| 作者单位： | 上海大学管理学院, 上海 200444 |
| |
| 基金项目： | 国家自然科学基金（Nos.11571221，11871327） |
| |
| 摘 要： | 研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是NP-难的,而且不存在完全多项式时间近似方案(fully polynomial time approximation scheme,简记为FPTAS).提出两个启发式算法,利用数值模拟比较它们的性能,并且将这两个启发式算法的解与最优解的上界进行比较.
|
| 关 键 词： | 排序 子工件工期 启发式算法 |
| 收稿时间： | 2017-05-19 |
Scheduling with sub-jobs' due dates |
| |
| ZHONG Weiya,YANG Ruoyao. Scheduling with sub-jobs' due dates[J]. OR Transactions, 2019, 23(2): 67-74. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.006 |
| |
| Authors: | ZHONG Weiya YANG Ruoyao |
| |
| Affiliation: | School of Management, Shanghai University, Shanghai 200444, China |
| |
| Abstract: | In this paper, we study a single machine scheduling problem in which sub-jobs have due dates. Given a set of jobs, each job is divided into several sub-jobs and each sub-job has a due date. A job is completed on time only if all its sub-jobs are completed before their due dates. We prove that even if each job has two sub-jobs, this problem is NP-hard and there is no FPTAS for this special case. Furthermore, we propose two heuristics for this model and a heuristic to get an upper bound and carry out numerical experiments to compare their performances. |
| |
| Keywords: | scheduling sub-job's due date heuristic algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
|
