Online scheduling of two identical machines under a grade of service provision
详细信息 查看官网全文
- 英文论文题名：Online scheduling of two identical machines under a grade of service provision
- 论文作者：Shuang Cai ; Ao Liu ; Ke Liu
- 英文论文作者：Shuang Cai ; Ao Liu ; Ke Liu ; Academy of Mathematics and Systems Science ; Chinese Academy of Sciences ; Key Laboratory Management ; Decision and Information Systems ; CAS ; University of Chinese Academy of Sciences ; School of management ; Wuhan University of Science and Technoledge ; Hubei Province ; Key laboratory of Intellegent Information Processing and Real-time Industry System
- 年：2017
- 作者机构：Academy of Mathematics and Systems Science,Chinese Academy of Sciences;Key Laboratory Management,Decision and Information Systems,CAS;University of Chinese Academy of Sciences;School of management,Wuhan University of Science and Technoledge;Hubei Province,Key laboratory of Intellegent Information Processing and Real-time Industry System;
- 英文论文关键词：Online scheduling ; Scheduling of two machines ; Competitive ratio ; Online algorithm
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（B）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
- 语种：英文
- 分类号：TP301.6
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：5
- 文件大小：163k
- 原文格式：D
- 会议级别：全国
摘要
In this paper, we consider the problem of two identical machines scheduling that jobs are processed under a grade of service(GoS) provision. The jobs arrive over time and the two machines can be idle at the same time only when all the jobs arrived are completed. To our best knowledge, this problem has never been studied so far. For the problem with objective makespan minimization, we prove that any online algorithm without delay has a competitive ratio of at least (5~(1/2)+1)/2.Finally, we develop an algorithm with competitive ratio 5/3, which is a very effective online algorithm.
In this paper, we consider the problem of two identical machines scheduling that jobs are processed under a grade of service(GoS) provision. The jobs arrive over time and the two machines can be idle at the same time only when all the jobs arrived are completed. To our best knowledge, this problem has never been studied so far. For the problem with objective makespan minimization, we prove that any online algorithm without delay has a competitive ratio of at least (5~(1/2)+1)/2.Finally, we develop an algorithm with competitive ratio 5/3, which is a very effective online algorithm.
In this paper, we consider the problem of two identical machines scheduling that jobs are processed under a grade of service(GoS) provision. The jobs arrive over time and the two machines can be idle at the same time only when all the jobs arrived are completed. To our best knowledge, this problem has never been studied so far. For the problem with objective makespan minimization, we prove that any online algorithm without delay has a competitive ratio of at least (5~(1/2)+1)/2.Finally, we develop an algorithm with competitive ratio 5/3, which is a very effective online algorithm.
引文
[1]K.Lee,J.Y.T.Leung,M.L,Pinedo,Makespan minimization in online scheduling with machine eligibility,Annals of Operations Research,204(1):189-222,2013.
[2]B.Chen,A.P.A.Vestjens,Scheduling on identical machines:How good is LPT in an on-linesetting,Operations Research Letters,21:165-169,1997.
[3]J.Park,S.Y.Chang,K.Lee,Online and semi-online scheduling of two machines under a grade of service provision,Operations Research Letters,34:692-696,2006.
[4]Y.Wu,M.Ji,Q.Yang,Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision,International Journal of Production Economics,135(1):367-371,2012.
[5]K.Lee,J.Y.T.Leung,M.L.Pinedo,Scheduling jobs with equal processing times subject to machine eligibility constraints,Journal of Scheduling,14(1):27-38,2010.
[6]L.Y.Hou,Online hierarchical service scheduling on two identical machines with release times,Operations Research Transactions,20(2):49-58,2016.In Chinese.
[7]Lu X,Liu Z,Semi-online scheduling problems on two uniform machines under a grade of service provision[J].Theoretical Computer Science,2013,489:58-66.
[8]Luo T,Xu Y,Optimal algorithm for semi-online scheduling on two machines under Go S levels[J].Optimization Letters,10(1):207-213,2016.
[9]Hu J,Jiang Y,Zhou P,et al,Total completion time minimization in online hierarchical scheduling of unit-size jobs[J],Journal of Combinatorial Optimization,2016:1-16.
[10]Noga J,Seiden S S.An optimal online algorithm for scheduling two machines with release times,Theoretical Computer Science,268(1):133-143,2001.
[11]Hong K S,Leung J Y T.On-line scheduling of real-time tasks,Real-Time Systems Symposium,Proceedings,IEEE,1988:244-250.
[12]Xu J,Liu Z H.An Optimal Online Algorithm for Scheduling on Two Parallel Machines with Go S Eligibility Constraints,Journal of the Operations Research Society of China,4(3):371-377,2016.
[13]R.L.Graham,E.L.Lawler,J.K.Lenstra,et al,Optimization and approximation in deterministic sequencing and scheduling:A survey,Annals of Discrete Mathematics,5:287-326,1979.
[2]B.Chen,A.P.A.Vestjens,Scheduling on identical machines:How good is LPT in an on-linesetting,Operations Research Letters,21:165-169,1997.
[3]J.Park,S.Y.Chang,K.Lee,Online and semi-online scheduling of two machines under a grade of service provision,Operations Research Letters,34:692-696,2006.
[4]Y.Wu,M.Ji,Q.Yang,Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision,International Journal of Production Economics,135(1):367-371,2012.
[5]K.Lee,J.Y.T.Leung,M.L.Pinedo,Scheduling jobs with equal processing times subject to machine eligibility constraints,Journal of Scheduling,14(1):27-38,2010.
[6]L.Y.Hou,Online hierarchical service scheduling on two identical machines with release times,Operations Research Transactions,20(2):49-58,2016.In Chinese.
[7]Lu X,Liu Z,Semi-online scheduling problems on two uniform machines under a grade of service provision[J].Theoretical Computer Science,2013,489:58-66.
[8]Luo T,Xu Y,Optimal algorithm for semi-online scheduling on two machines under Go S levels[J].Optimization Letters,10(1):207-213,2016.
[9]Hu J,Jiang Y,Zhou P,et al,Total completion time minimization in online hierarchical scheduling of unit-size jobs[J],Journal of Combinatorial Optimization,2016:1-16.
[10]Noga J,Seiden S S.An optimal online algorithm for scheduling two machines with release times,Theoretical Computer Science,268(1):133-143,2001.
[11]Hong K S,Leung J Y T.On-line scheduling of real-time tasks,Real-Time Systems Symposium,Proceedings,IEEE,1988:244-250.
[12]Xu J,Liu Z H.An Optimal Online Algorithm for Scheduling on Two Parallel Machines with Go S Eligibility Constraints,Journal of the Operations Research Society of China,4(3):371-377,2016.
[13]R.L.Graham,E.L.Lawler,J.K.Lenstra,et al,Optimization and approximation in deterministic sequencing and scheduling:A survey,Annals of Discrete Mathematics,5:287-326,1979.