[1]刘其佳张利齐冯琪.考虑运输的退化工作在线排序问题研究[J].郑州大学学报(工学版),2015,36(02):125-128.[doi:10.3969/j. issn.1671 -6833.2015.02.027]
　LIU Qi-jia,ZHANG Li-qi.FENG Qi.Research on Online Scheduling with Deteriorating Jobs and Delivery Times[J].Journal of Zhengzhou University (Engineering Science),2015,36(02):125-128.[doi:10.3969/j. issn.1671 -6833.2015.02.027]
点击复制

考虑运输的退化工作在线排序问题研究()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
36
期数:
2015年02期
页码:
125-128
栏目:
出版日期:
2015-04-30

文章信息/Info

Title:
Research on Online Scheduling with Deteriorating Jobs and Delivery Times
作者:
刘其佳1张利齐2冯琪3
1.郑州大学数学与统计学院,河南郑州450001;2.河南农业大学信息与管理科学学院,河南郑州450003 ;3.中原工学院理学院,河南郑州450007
Author(s):
LIU Qi-jia1; ZHANG Li-qi2.FENG Qi1
1.School of Mathematics and Statistics ,Zhengzhou University , Zhenghou 450001 , China; 2.College of Information and Man-agement Science，Henan Agricultural University , Zhengzhou 450003,China; 3.College of Science，Zhongyuan University ofTechnology ,Zhengzhou 450007，China
关键词:
排序; 退化工件; 运输
Keywords:
scheduling;  deteriorating jobs;  delivery
分类号:
O223
DOI:
10.3969/j. issn.1671 -6833.2015.02.027
文献标志码:
A
摘要:
本文研究了单台机器上工件具有退化效应并且需要考虑工件运输的在线排序问题.目标函数是最小化最大运输完工时间.对于这个在线排序问题,主要是设计一个有效的在线算法.首先采用对手法找到问题的下界,即设计一个坏实例,使得算法得到的目标值与离线最优目标值的比尽可能的大,之后依据下界设计给出一个在线算法.通过对手法的应用,给出问题的下界,并设计了一个竞争比为2的在线算法.
Abstract:
In this paper,we study the online scheduling on a single machine with deteriorating jobs and deliv-ery times.The objective function is to minimize the maximum delivery completion time of these jobs. For thisonline scheduling problem,the objective is to design an effective online algorithm. We establish a lower boundby adversary strategy, i.e,design a bad instance to make the ratio of the objective by online algorithm andoffine objective as big as possible,then we present an online algorithm by this lower bound. Thus we get alower bound by adversary strategy and an online algorithm with the competitive ratio of 2.
更新日期/Last Update: