[1]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]
Copy
Journal of Zhengzhou University (Engineering Science)[ISSN
1671-6833/CN
41-1339/T] Volume:
36卷
Number of periods:
2015 02
Page number:
125-128
Column:
Public date:
2015-04-30
- Title:
-
Research on Online Scheduling with Deteriorating Jobs and Delivery Times
- 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
- CLC:
-
O223
- DOI:
-
10.3969/j. issn.1671 -6833.2015.02.027
- 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.