More Web Proxy on the site http://driver.im/

article

Optimal algorithms for online single machine scheduling with deteriorating jobs

Authors:

Jiazhen HuoAuthors Info & Claims

Theoretical Computer Science, Volume 445

Pages 75 - 81

https://doi.org/10.1016/j.tcs.2012.05.004

Published: 01 August 2012 Publication History

Abstract

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. In this paper we study online single machine scheduling for deteriorating jobs, where jobs arrive over time and become known to any online algorithm on their arrivals. The processing time of each job is a linearly increasing function of its start time. We mainly investigate three online models that minimize makespan, total completion time and maximum delivery time, respectively. For each model we present an optimal online algorithm in competitiveness.

References

[1]

Borodin, A. and El-Yaniv, R., Online Computation and Competitive Analysis. 1998. Cambridge University Press, Cambridge.

[2]

Chen, B. and Vestjens, A.P.A., Scheduling on identical machines: How good is lpt in an online setting?. Operations Research Letters. v21. 165-169.

[3]

Cheng, Y.S. and Sun, S.J., Scheduling linear deteriorating jobs with rejection on a single machine. European Journal of Operational Research. v194. 18-27.

[4]

Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics. v5. 287-326.

[5]

Hoogeveen, J.A. and Vestjens, A.P.A., A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine. SIAM Journal on Discrete Mathematics. v13. 56-63.

[6]

Ji, M. and Cheng, T.C.E., Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan. European Journal of Operational Research. v202. 90-98.

[7]

Kise, H., Iberaki, T. and Mine, H., Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times. Journal of Operation Research Society Japan. v22. 205-224.

[8]

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B., Sequencing and scheduling: algorithms and complexity. In: Graves, S.C., Zipkin, P.H., Rinnooy Kan, A.H.G. (Eds.), Handbooks of Operation Research Management Science, vol. 4. North-Holland, Amsterdam. pp. 445-522.

[9]

Lu, X., Sitters, R.A. and Stougie, L., A class of on-line scheduling algorithms to minimize total completion time. Operations Research Letters. v31. 232-236.

[10]

Mosheiov, G., Scheduling jobs under simple linear deterioration. Computers and Operations Research. v21. 653-659.

[11]

Ng, C.T., Li, S.S., Cheng, T.C.E. and Yuan, J.J., Preemptive scheduling with simple linear deterioration on a single machine. Theoretical Computer Science. v411. 3578-3586.

[12]

Pruhs, K., Sgall, J. and Torng, E., Online scheduling. In: Leung, J.Y.-T. (Ed.), Handbook of Scheduling: Algorithms, Models, and Performance Analysis,

[13]

Shmoys, D.B., Wein, J. and Williamson, D.P., Scheduling parallel machines online. SIAM Journal on Computing. v24. 1313-1331.

[14]

Stee, R.V. and Poutre, H.L., Minimizing the total completion time on-line on a single machine, using restarts. Journal of Algorithms. v57. 95-129.

[15]

Tian, J., Fu, R.Y. and Yuan, J.J., A best on-line algorithm for single machine scheduling with small delivery times. Theoretical Computer Science. v393. 287-293.

[16]

A.P.A. Vestjens, On-line machine scheduling, Ph.D. Thesis, Eindhoven Unversity of Technology, Netherlands, 1997.

Cited By

Chai XLi WYuan HWang L(2022)Online scheduling on a single machine with linear deteriorating processing times and delivery timesJournal of Combinatorial Optimization10.1007/s10878-020-00557-544:3(1900-1912)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10878-020-00557-5
Ma RTao JYuan J(2016)Online scheduling with linear deteriorating jobs to minimize the total weighted completion timeApplied Mathematics and Computation10.1016/j.amc.2015.10.058273:C(570-583)Online publication date: 15-Jan-2016
https://dl.acm.org/doi/10.1016/j.amc.2015.10.058

Optimal algorithms for online single machine scheduling with deteriorating jobs
1. Computing methodologies
  1. Artificial intelligence
2. Theory of computation

Recommendations

Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

In this paper, we consider the problem of scheduling n deteriorating jobs with release dates on a single (batching) machine. Each job's processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 445, Issue

August, 2012

98 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2012.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 August 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chai XLi WYuan HWang L(2022)Online scheduling on a single machine with linear deteriorating processing times and delivery timesJournal of Combinatorial Optimization10.1007/s10878-020-00557-544:3(1900-1912)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10878-020-00557-5
Ma RTao JYuan J(2016)Online scheduling with linear deteriorating jobs to minimize the total weighted completion timeApplied Mathematics and Computation10.1016/j.amc.2015.10.058273:C(570-583)Online publication date: 15-Jan-2016
https://dl.acm.org/doi/10.1016/j.amc.2015.10.058

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents