机器带有不可用区间的可拒绝平行机排序问题

• 作者: 池晶晶
• 来源期刊: 曲阜师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 排序 拒绝 不可用区间 退化效应
• 年，卷（期）: 2016,（3）
• 所属期刊栏目: 数学科学
• 页码范围: 42-48
• 页数: 7页
• 分类号: O224
• 字数: 1874字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5337.2016.3.042

摘要

主要研究了机器带有拒绝和不可用区间的可拒绝排序问题.针对这一问题的两种情形进行研究.一方面,考虑了每台机器有一个不可用区间,且目标函数是极小化总完工时间与拒绝费用之和的平行机排序问题.另一方面,考虑了工件的实际加工时间是开始时间的按比例函数的平行机排序问题,并且每台机器在一段特定的区间内不可用.当然,可以通过支付拒绝惩罚费用而拒绝加工工件,这一问题的目标是极小化总加权完工时间与拒绝费用之和.对于以上两个问题,分别给出了时间复杂性为O(nm(m∏i=1Si)(Pn)m))和O(nm∏i=1(Si-t0)m∏i=1(An)m)的伪多项式时间动态规划算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	池晶晶	曲阜师范大学管理学院	4	0	0.0	0.0