Article

Optimal On-Line Algorithms for Single-Machine Scheduling

Authors:

Han Hoogeveen,

Arjen P. A. VestjensAuthors Info & Claims

Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization

Pages 404 - 414

Published: 03 June 1996 Publication History

Abstract

No abstract available.

Cited By

View all

Tian BHuang JMozafari BSchoenebeck G(2018)Contention-aware lock scheduling for transactional databasesProceedings of the VLDB Endowment10.1145/3187009.317774011:5(648-662)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1145/3187009.3177740
Tian BHuang JMozafari BSchoenebeck G(2018)Contention-aware lock scheduling for transactional databasesProceedings of the VLDB Endowment10.1145/3177732.317774011:5(648-662)Online publication date: 5-Oct-2018
https://dl.acm.org/doi/10.1145/3177732.3177740
Lübbecke EMaurer OMegow NWiese A(2016)A New Approach to Online SchedulingACM Transactions on Algorithms10.1145/299680013:1(1-34)Online publication date: 21-Dec-2016
https://dl.acm.org/doi/10.1145/2996800
Show More Cited By

Optimal On-Line Algorithms for Single-Machine Scheduling
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Single machine parallel-batch scheduling with deteriorating jobs

We consider several single machine parallel-batch scheduling problems in which the processing time of a job is a linear function of its starting time. We give a polynomial-time algorithm for minimizing the maximum cost, an O(n⁵) time algorithm for ...
Single machine scheduling problems with deteriorating jobs

This paper considers the single machine scheduling problems with deteriorating jobs, i.e. jobs whose processing times are a decreasing linear function of their starting time. It is assumed that jobs have the different basic processing time and same ...
Optimal algorithms for online single machine scheduling with deteriorating jobs

In many realistic scenarios of job processing, one job consumes a longer time to be satisfied with a later start time of processing. This phenomenon is known as job's deterioration effect. Such effect is unexplored in the context of online environment. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization

June 1996

504 pages

ISBN:3540613102

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 03 June 1996

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tian BHuang JMozafari BSchoenebeck G(2018)Contention-aware lock scheduling for transactional databasesProceedings of the VLDB Endowment10.1145/3187009.317774011:5(648-662)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1145/3187009.3177740
Tian BHuang JMozafari BSchoenebeck G(2018)Contention-aware lock scheduling for transactional databasesProceedings of the VLDB Endowment10.1145/3177732.317774011:5(648-662)Online publication date: 5-Oct-2018
https://dl.acm.org/doi/10.1145/3177732.3177740
Lübbecke EMaurer OMegow NWiese A(2016)A New Approach to Online SchedulingACM Transactions on Algorithms10.1145/299680013:1(1-34)Online publication date: 21-Dec-2016
https://dl.acm.org/doi/10.1145/2996800
Fang YLu X(2016)Online parallel-batch scheduling to minimize total weighted completion time on single unbounded machineInformation Processing Letters10.1016/j.ipl.2016.03.010116:8(526-531)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.ipl.2016.03.010
(2016)Adaptive online scheduling of tasks with anytime property on heterogeneous resourcesComputers and Operations Research10.1016/j.cor.2016.06.00876:C(95-117)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.cor.2016.06.008
Feng XCheng YZheng FXu Y(2016)Online integrated production---distribution scheduling problems without preemptionJournal of Combinatorial Optimization10.1007/s10878-015-9841-631:4(1569-1585)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1007/s10878-015-9841-6
Lin YThai MWang CLai Y(2015)Two-tier project and job scheduling for SaaS cloud service providersJournal of Network and Computer Applications10.1016/j.jnca.2015.02.00852:C(26-36)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1016/j.jnca.2015.02.008
Günther EMaurer OMegow NWiese AKhanna S(2013)A new approach to online schedulingProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627826(118-128)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627826
Yuan JNg CCheng T(2011)Best semi-online algorithms for unbounded parallel batch schedulingDiscrete Applied Mathematics10.1016/j.dam.2011.01.003159:8(838-847)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1016/j.dam.2011.01.003
Chung CNonner TSouza ACharikar M(2010)SRPT is 1.86-competitive for completion time schedulingProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873712(1373-1388)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873712
Show More Cited By

Abstract

Cited By

Recommendations

Single machine parallel-batch scheduling with deteriorating jobs

Single machine scheduling problems with deteriorating jobs

Optimal algorithms for online single machine scheduling with deteriorating jobs

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations