工件具有子工件工期的排序问题

doi:10.15960/j.cnki.issn.1007-6093.2019.02.006

运筹学学报 ›› 2019, Vol. 23 ›› Issue (2): 67-74.doi: 10.15960/j.cnki.issn.1007-6093.2019.02.006

工件具有子工件工期的排序问题

仲维亚^*, 杨若瑶

上海大学管理学院, 上海 200444

收稿日期:2017-05-19 出版日期:2019-06-15 发布日期:2019-06-15
通讯作者: 仲维亚 E-mail:wyzhong@shu.edu.cn
基金资助:
国家自然科学基金（Nos.11571221，11871327）

Scheduling with sub-jobs' due dates

ZHONG Weiya^*, YANG Ruoyao

School of Management, Shanghai University, Shanghai 200444, China

Received:2017-05-19 Online:2019-06-15 Published:2019-06-15

摘要/Abstract

摘要： 研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成，每个子工件都有各自的工期.只有当工件的每个子工件都按时完成，才能称该工件是按时完工工件，否则，称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时，该问题是NP-难的，而且不存在完全多项式时间近似方案（fully polynomialtime approximation scheme，简记为FPTAS）.提出两个启发式算法，利用数值模拟比较它们的性能，并且将这两个启发式算法的解与最优解的上界进行比较.

关键词: 排序, 子工件工期, 启发式算法

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.

Key words: scheduling, sub-job's due date, heuristic algorithm

中图分类号:

O223

仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74.

ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates[J]. Operations Research Transactions, 2019, 23(2): 67-74.

参考文献 9

[1]	Moore J M. An job, one machine sequencing algorithm for minimizing the number of late jobs[J]. Management Science, 1968, 15:102-109.
[2]	Lenstra J K, Kan Rinnooy A H G, Brucker P. Complexity of machine scheduling problems[J]. Annals of Discrete Mathematics, 1977, 1:343-362.
[3]	Stéphane D P, Sevaux M. An exact method to minimize the number of tardy jobs in single machine scheduling[J]. Journal of Scheduling, 2004, 7:405-420.
[4]	Chen B, Potts C N, Strusevich V A. Approximation algorithms for two-machine flow shop scheduling with batch setup times[J]. Mathematical Programming, 1998, 82:255-271.
[5]	Gong H, Tang L, Leung J Y T. Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost[J]. Naval Research Logistics, 2016, 63:492-502.
[6]	Liu L L, Ng C T, Cheng T C E. On the complexity of bi-criteria scheduling on a single batch processing machine[J]. Journal of Scheduling, 2010, 13, 629-638.
[7]	Liu Z, Yuan J, Cheng T C E. On scheduling an unbounded batch machine[J]. Operations Research Letters, 2003, 31, 42-48.
[8]	Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NPCompleteness[M]. New York:Freeman, 1979.
[9]	Woeginger G J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?[J]. Informs Journal on Computing, 2000, 12:57-74.

[1]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.
[2]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[3]	陆书翔, 吕长虹, 秦涛. 集装箱码头桥机调度问题基于完工时间下界的算法[J]. 运筹学学报, 2020, 24(3): 67-76.
[4]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[5]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[6]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[7]	苟燕, 戴秦, 张新功. 具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报, 2019, 23(4): 86-94.
[8]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[9]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[10]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[11]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[12]	蔡爽, 杨珂, 刘克. 具有机器适用限制的分布式置换流水车间问题的模型与算法[J]. 运筹学学报, 2018, 22(4): 17-30.
[13]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[14]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[15]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.

工件具有子工件工期的排序问题

Scheduling with sub-jobs' due dates

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 9

相关文章 15

编辑推荐

Metrics

本文评价