nach oben

Journal of Scheduling

Erschienen in:

01.04.2014

Online scheduling with preemption or non-completion penalties

verfasst von: Stanley P. Y. Fung

Erschienen in: Journal of Scheduling | Ausgabe 2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider online preemptive scheduling problems where jobs have deadlines and the objective is to maximize the total weight of jobs completed before their deadlines. In the first problem, preemptions are not free but incur a penalty. In the second problem, a job has to be accepted or rejected immediately upon arrival, and may need to be immediately allocated a fixed scheduling interval as well; if these accepted jobs are not eventually completed, the job is lost, and a penalty is incurred. We give an algorithm with the optimal competitive ratio for the first problem, and new and improved algorithms for the second problem, under different models of preemptions and job weights.

Vorheriger Artikel Minimizing total weighted completion time with an unexpected machine unavailable interval

Nächster Artikel A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Baruah, S. K., Koren, G., Mao, D., Mishra, B., Raghunathan, A., Rosier, L. E., et al. (1992). On the competitiveness of on-line real-time task scheduling. Real-Time Systems, 4, 125–144.CrossRef

Ding, J., Ebenlendr, T., Sgall, J., & Zhang, G. (2007). Online scheduling of equal-length jobs on parallel machines. In Proceedings of 15th European Symposium on Algorithms, Vol. 4698 of Lecture Notes in Computer Science (pp. 427–438). New York: Springer.

Ding, J., & Zhang, G. (2006). Online scheduling with hard deadlines on parallel machines. In Proceedings of 2nd International Conference on Algorithmic Aspects in Information and Management, Vol. 4041 of Lecture Notes in Computer Science (pp. 32–42). New York: Springer.

Dürr, C., Jez, L., & Nguyen, K. T. (2009). Online scheduling of bounded length jobs to maximize throughput. In Proceedings of 7th International Workshop in Approximation and Online Algorithms, Vol. 5893 of Lecture Notes in Computer Science (pp. 116–127). New York: Springer.

Ebenlendr, T., & Sgall, J. (2008). A lower bound for scheduling of unit jobs with immediate decision on parallel machines. In Proceedings of 6th Workshop on Approximation and Online Algorithms, Vol. 5426 of Lecture Notes in Computer Science (pp. 43–52). New York: Springer.

Fung, S. P. Y. (2008). Lower bounds on online deadline scheduling with preemption penalties. Information Processing Letters, 108(4), 214–218.CrossRef

Fung, S. P. Y., Zheng, F., Chan, W.-T., Chin, F. Y. L., Poon, C. K., & Wong, P. W. H. (2008). Improved on-line broadcast scheduling with deadlines. Journal of Scheduling, 11(4), 299–308.CrossRef

Goldwasser, M. H., & Kerbikov, B. (2003). Admission control with immediate notification. Journal of Scheduling, 6, 269–285.CrossRef

Hoogeveen, H., Potts, C. N., & Woeginger, G. J. (2000). On-line scheduling on a single machine: Maximizing the number of early jobs. Operations Research Letters, 27(5), 193–197.CrossRef

Koren, G., & Shasha, D. (1995). \(D^{over}\): An optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM Journal on Computing, 24, 318–339.CrossRef

Nguyen, K. T. (2011). Improved online scheduling in maximizing throughput of equal length jobs. In Proceedings of 6th International Computer Science Symposium in Russia, Vol. 6651 of Lecture Notes in Computer Science (pp. 429–442). New York: Springer.

Thibault, N., & Laforest, C. (2009). Online time constrained scheduling with penalties. In Proceedings of 23rd IEEE International Symposium on Parallel and Distributed Processing.

Ting, H.-F. (2006). A near optimal scheduler for on-demand data broadcasts. In Proceedings of 6th Italian Conference on Algorithms and Complexity, Vol. 3998 of Lecture Notes in Computer Science (pp. 163–174). New York: Springer.

Woeginger, G. J. (1994). On-line scheduling of jobs with fixed start and end times. Theoretical Computer Science, 130(1), 5–16.CrossRef

Zheng, F., Dai, W., Xiao, P., & Zhao, Y. (2005). Competitive strategies for on-line production order disposal problem. In Proceedings of 1st International Conference on Algorithmic Applications in Management (pp. 46–54).

Zheng, F., Xu, Y., & Poon, C. K. (2009). On job scheduling with preemption penalties. In Proceedings of 5th International Conference on Algorithmic Aspects in Information and Management, Vol. 5564 of Lecture Notes in Computer Science (pp. 315–325). New York: Springer.

Titel: Online scheduling with preemption or non-completion penalties
verfasst von: Stanley P. Y. Fung
Publikationsdatum: 01.04.2014
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 2/2014
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-013-0321-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2014

The total adjustment cost problem: Applications, models, and solution algorithms

A sequential GRASP for the therapist routing and scheduling problem

A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem

Approximation schemes for single machine scheduling with non-renewable resource constraints

The optimal number of used machines in a two-stage flexible flowshop scheduling problem

Minimizing total weighted completion time with an unexpected machine unavailable interval