[1]刘澈,罗成新. 带到达时间、不可用区间、拒绝工件的单机排序问题 (三峡地区资源环境生态研究)[J].重庆师范大学学报(自然科学版),2013,30(01):17-20.[doi:10.11721/cqnuj20130104]
LIU Che,LUO Cheng-xin. Single Machine Scheduling Problem with Release Dates,Rejection and an Unavailable Interval [J].期刊社,2013,30(01):17-20.[doi:10.11721/cqnuj20130104]
点击复制
带到达时间、不可用区间、拒绝工件的单机排序问题 (三峡地区资源环境生态研究)
(PDF)
重庆师范大学学报(自然科学版)[ISSN:1672-6693/CN:50-1165/N]
- 卷:
-
30
- 期数:
-
2013年01期
- 页码:
-
17-20
- 栏目:
-
运筹学与控制论
- 出版日期:
-
2013-01-25
文章信息/Info
- Title:
-
Single Machine Scheduling Problem with Release Dates,Rejection and an Unavailable Interval
- 作者:
-
刘澈; 罗成新
-
- Author(s):
-
LIU Che; LUO Cheng-xin
-
-
- 关键词:
-
到达时间; 拒绝工件; 不可用区间; 时间表长
- Keywords:
-
-
- 分类号:
-
-
- DOI:
-
10.11721/cqnuj20130104
- 文献标志码:
-
A
- 摘要:
-
考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个工件。本文的目标函数是极小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出了一个近似算法,并通过引理1证明出此算法是3因子算法;其次提出了一个动态规划算法,然后通过修改这个动态规划算法的执行过程来减少运行时间,进而得到了一个全多项式时间近似方案,证明出该方案的时间复杂性为O JB( SX n 2 ε SX) JB 。
- Abstract:
-
-
更新日期/Last Update:
2013-01-26