[1]顾燕红.有宽容交货期的加权超前延误工件数问题[J].深圳大学学报理工版,2006,23(3):278-282.
 GU Yan-hong.Minimizing weighted number of early and tardy jobs with a common due window[J].Journal of Shenzhen University Science and Engineering,2006,23(3):278-282.
点击复制

有宽容交货期的加权超前延误工件数问题()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第23卷
期数:
2006年3期
页码:
278-282
栏目:
生命科学
出版日期:
2006-07-30

文章信息/Info

Title:
Minimizing weighted number of early and tardy jobs with a common due window
文章编号:
1000-2618(2006)03-0278-05
作者:
顾燕红
深圳大学理学院,深圳518060
Author(s):
GU Yan-hong
College of Science Shenzhen University
关键词:
共同宽容交货期加权工件多项式算法动态规划算法近似算法背包问题超前延误工件
Keywords:
common due window weighted job polynomial approach dynamic programming algorithm approximate scheme knapsack problem early /tardy job
分类号:
O 223
文献标志码:
A
摘要:
研究加权超前延误工件数问题.在单机存在非限制性共同宽容交货期(commom due window,CDW)条件下,给出一个动态规划算法及一个近似算法;对单机限制性CDW中的某个特殊情况,给出一个多项式时间算法;对两台平行机非限制性CDW情况,构建一个伪多项式时间动态规划算法,证明其是一般意义下的NP-hard问题.
Abstract:
There are a number of jobs with a common due window(CDW)to be processed on one certain machine facility. The objective is to minimize the total weighted number of early and tardy jobs for three different machine situations. A dynamic programming algorithm(DPA)and an approximate scheme are developed for the single machine situation with an unrestricted CDW. This DPA needs only the similar pseudo-polynomial computational time with that of knapsack problem. A polynomial approach is established for a special case of the single machine situation with a restricted CDW. For the situation of two parallel machines with an unrestricted CDW, another novel DPA still running in pseudo-polynomial time is presented, which shows that this situation is ordinary NP-hard.
更新日期/Last Update: 2015-06-26