THE NP-HARDNESS OF THE SINGLE MACHINE COMMON DUE DATE WEIGHTED TARDINESS PROBLEM 被引量：10

THE NP-HARDNESS OF THE SINGLE MACHINE COMMON DUE DATE WEIGHTED TARDINESS PROBLEM

导出

摘要 In this paper we prove that the single machine common due dateweighted tardiness problem is NP-hard. In this paper we prove that the single machine common due dateweighted tardiness problem is NP-hard.

作者 YUAN Jinjiang (Department of Mathematics,Zhengzhou University,Zhengzhou 450052,China)

出处《Systems Science and Mathematical Sciences》 SCIE EI CSCD 1992年第4期328-333,共6页

基金 This work is supported by the National Natural Science Foundation of China

关键词 DUE DATE TARDINESS NP-COMPLETE Due date tardiness NP-complete

分类号 N94 [自然科学总论—系统科学]

引文网络
相关文献

同被引文献11

1CHENG Ming-bao SUN Shi-jie.The single-machine scheduling problems with deteriorating jobs and learning effect[J].Journal of Zhejiang University-Science A(Applied Physics & Engineering),2006,7(4):597-601. 被引量：12
2余英,卢圳,孙世杰,何龙敏,胡晶地.Scheduling problems on tardiness penalty and earliness award with simply linear processing time[J].Journal of Shanghai University(English Edition),2009,13(2):123-128. 被引量：2
3陶明子,赵传立.具有安装时间和学习效应的单机排序问题[J].运筹与管理,2010,19(4):101-107. 被引量：2
4何少龙,赵传立.有安装时间的单机排序问题[J].沈阳师范大学学报（自然科学版）,2011,29(2):138-141. 被引量：1
5余英,罗永超,程明宝.带分批的一类具有恶化加工时间的排序问题的算法研究[J].湘潭大学自然科学学报,2013,35(2):14-16. 被引量：5
6陈立忠,杨栋,张玉忠.供应链排序中的外包问题[J].重庆师范大学学报（自然科学版）,2013,30(5):21-26. 被引量：1
7吴春燕,孙世杰.货物装卸中的一个排序问题[J].运筹学学报,2000,4(4):1-11. 被引量：13
8陈荣军,唐国春.单机上的排序与转包问题[J].应用数学学报,2017,40(2):170-178. 被引量：1
9张新功,刘甲玉,崔同欣.误工工件个数和最大费用函数的单机双代理KS公平定价问题[J].重庆师范大学学报（自然科学版）,2020,37(1):16-21. 被引量：2
10宋政芳,孙世杰,吴春燕.一个超前有奖迟后受罚的排序问题(英文)[J].运筹学学报,2002,6(4):31-36. 被引量：7

引证文献10

1陆焱萍,孙世杰,谭芳.货物装卸中带共同宽容期的排序问题[J].上海大学学报（自然科学版）,2006,12(2):174-180.
2王利,孙世杰.一个可拒装卸引发的排序问题[J].应用科学学报,2007,25(3):283-287.
3余英,孙世杰,何龙敏.A dynamic programming algorithm for scheduling problems on earliness award and tardiness penalty with time-dependent processing time[J].Journal of Shanghai University(English Edition),2008,12(3):204-209. 被引量：1
4余英,孙世杰,王凯,何龙敏.具有学习效应的超前有奖延误受罚的排序问题(英文)[J].运筹学学报,2010,14(4):41-52. 被引量：2
5余英,邓从政,曾春花.具有安装时间和共同交货期的单机排序问题[J].重庆师范大学学报（自然科学版）,2015,32(1):16-21.
6张喆,李文华.问题1|d_j=d|Σw_jT_j的一个全多项式近似方案[J].数学杂志,2015,35(4):1005-1011.
7李寒雪,樊保强,陈继文,郭志佳,杨燕英,李欣.工件可外包的单机准时排序问题[J].重庆师范大学学报（自然科学版）,2019,36(6):15-21.
8张新功,崔同欣.共同工期下的总权误工单机双代理排序问题[J].重庆师范大学学报（自然科学版）,2022,39(1):35-40. 被引量：4
9宋政芳,孙世杰,吴春燕.一个超前有奖迟后受罚的排序问题(英文)[J].运筹学学报,2002,6(4):31-36. 被引量：7
10余英.带指数学习效应的一类提前延误排序问题[J].凯里学院学报,2016,34(3):17-20.

二级引证文献13

1陆焱萍,孙世杰,谭芳.货物装卸中带共同宽容期的排序问题[J].上海大学学报（自然科学版）,2006,12(2):174-180.
2王利,孙世杰.一个可拒装卸引发的排序问题[J].应用科学学报,2007,25(3):283-287.
3余英,孙世杰,何龙敏.A dynamic programming algorithm for scheduling problems on earliness award and tardiness penalty with time-dependent processing time[J].Journal of Shanghai University(English Edition),2008,12(3):204-209. 被引量：1
4余英,卢圳,孙世杰,何龙敏,胡晶地.Scheduling problems on tardiness penalty and earliness award with simply linear processing time[J].Journal of Shanghai University(English Edition),2009,13(2):123-128. 被引量：2
5余英,孙世杰,王凯,何龙敏.具有学习效应的超前有奖延误受罚的排序问题(英文)[J].运筹学学报,2010,14(4):41-52. 被引量：2
6余英.加工时间与位置有关的一类排序问题[J].凯里学院学报,2011,29(3):17-19.
7何少龙,赵传立.有安装时间的单机排序问题[J].沈阳师范大学学报（自然科学版）,2011,29(2):138-141. 被引量：1
8余英,邓从政,曾春花.具有安装时间和共同交货期的单机排序问题[J].重庆师范大学学报（自然科学版）,2015,32(1):16-21.
9余英,舒彤,曾春花.工件带简单线性恶化函数和共同交货期单机排序问题[J].运筹与管理,2016,25(1):154-157.
10李中华,唐小敏,赵文平,张新功.固定区间下的可中断单机双代理总加权误工问题[J].重庆师范大学学报（自然科学版）,2023,40(1):15-20.

1Long, Yunliang.Electromagnetic　Field　Due　to　a　Loop　Antenna　Buried　in　a　Medium　with　Complex　Boundaries[J].Journal of Systems Engineering and Electronics,1994,5(2):19-25.
2LU Xiang\|nan School of Management, Zhejiang University, 20 Yugu Rd. Hangzhou 310027, China.Determination of Optimal Due-Date for Single-Machine Scheduling with Dynamic Programming Approach[J].Systems Science and Systems Engineering,2000,10(3):373-379.
3LI Ying\|juan\+1,\ WANG Ding\|wei\+2 1. Department of Industry and Business Administration, Shenyang University Shenyang 110013,China 2. Department of Systems Engineering, College of Information Science and Engineering,Northeastern University,Shenyan.Simulated Annealing for Earliness/Tardiness Production Planning Model[J].Systems Science and Systems Engineering,2000,10(1):93-98. 被引量：1
4ZENG Anjun SHA Jichang National University of Defence and Technology, Changsha 410073, China.Effective Neural Algorithms for Combinatorial Optimization[J].Systems Science and Systems Engineering,1993,3(4):326-333.
5刘炯朗,黄文奇,陈亮.A QUASI-PHYSICAL METHOD FOR SOLVING THE SCHEDULING PROBLEM OF SPACE UTILIZATION[J].Science China Mathematics,1991,34(9):1144-1152.
6Hongluan ZHAO,Guojun LI.UNBOUNDED BATCH SCHEDULING WITH A COMMON DUE WINDOW ON A SINGLE MACHINE[J].Journal of Systems Science & Complexity,2008,21(2):296-303. 被引量：2
7宋恩民,黄文奇.AN APPROXIMATELY FAST ALGORITHM FOR DECIDING THE VALIDITY OF DISJUNCTIVE NORMAL FORMS (DNFs)[J].Chinese Science Bulletin,1992,37(23):1947-1949.
8Zhang Cheng,Yang Jing,Xu Jin,Zhao DongMing.A DNA length reducing computing model for maximum independent set problem[J].Chinese Science Bulletin,2010,55(9):892-898. 被引量：1
9崔捷,王海龙,干福熹,黄旭光,蔡志岗,李庆行,余振新.TRANSIENT PHOTOLUMINESCENCE SPECTRA OF Ⅱ-Ⅵ WIDE GAP ZnSe/ZnS STRAINED-LAYER SUPERLATTICES[J].Chinese Science Bulletin,1992,37(20):1696-1699.
10YANG Xiao\|guang\+1\ \ ZHU Qing\+2 1.Laboratory of Management, Decision and Information Systems Institute of Systems Science, Academia Sinica, Beijing 100080, China 2.Department of Mathematics, Anhui University, Hefei 230039, China.A Heuristic Method for Some NP-hard Robust Combinatorial Optimization Problems[J].Systems Science and Systems Engineering,1999,9(3):356-363.

Systems Science and Mathematical Sciences

1992年第4期

浏览历史

内容加载中请稍等...

THE NP-HARDNESS OF THE SINGLE MACHINE COMMON DUE DATE WEIGHTED TARDINESS PROBLEM 被引量：10

同被引文献11

引证文献10

二级引证文献13

相关作者

相关机构

相关主题

浏览历史