Scheduling Jobs to Minimize a Convex Function of Resource Usage

• Autorzy: Szögi Evelin , Kis Tamas

Identyfikatory

DOI

10.15439/2023F4164

• Języki publikacji: EN

Abstrakty

EN

In this paper we describe polynomial time algorithms for minimizing a separable convex function of the resource usage over time of a set of jobs with individual release dates and deadlines, and admitting a common processing time.

Słowa kluczowe

EN

computer science; load management; approximation algorithm; convex function; scheduling; complexity theory

PL

informatyka; zarządzanie obciążeniem; algorytm; aproksymacja; funkcja wypukła; planowanie; teoria złożoności

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 791--799
• Opis fizyczny: Bibliogr. 14 poz., wz., tab., wykr., il.

Twórcy

autor

Szögi Evelin

• ELKH SZTAKI Kende str. 13-17, Budapest, 1111, Hungary
• Department of Operations Research Loránd Eötvös University

• https://orcid.org/0009-0008-5818-374X

autor

Kis Tamas

• ELKH SZTAKI Kende str. 13-17, Budapest, 1111, Hungary

• https://orcid.org/0000-0002-2759-1264

Bibliografia

• 1. Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network flows. Prentice-Hall, Inc., New Jersey, 1993.
• 2. Philippe Baptiste. Scheduling equal-length jobs on identical parallel machines. Discrete Applied Mathematics, 103(1):21–32, 2000.
• 3. Philippe Baptiste, Peter Brucker, Sigrid Knust, and Vadim G. Timkovsky. Ten notes on equal-processing-time scheduling. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2:111–127, 2004.
• 4. Jacek Błażewicz. Deadline scheduling of tasks with ready times and resource constraints. Information Processing Letters, 8(2):60–63, 1979.
• 5. Peter Brucker and Svetlana Kravchenko. Scheduling jobs with equal processing times and time windows on identical parallel machines. Journal of Scheduling, 11:229–237, 08 2008.
• 6. Mihai Burcea, Wing-Kai Hon, Hsiang-Hsuan Liu, Prudence W. Wong, and David K. Yau. Scheduling for electricity cost in a smart grid. Journal of Scheduling, 19(6):687–699, 2016.
• 7. Márton Drótos and Tamás Kis. Resource leveling in a machine environment. European Journal of Operational Research, 212(1):12–21, 2011.
• 8. Péter Györgyi, Tamás Kis, and Evelin Szögi. A polynomial time algorithm for solving the preemptive grid-scheduling problem. unpublished, 2023.
• 9. Bruce Hajek. Performance of global load balancing by local adjustment. IEEE Transactions on Information Theory, 36(6):1398–1414, 1990.
• 10. Nicholas JA Harvey, Richard E Ladner, László Lovász, and Tami Tamir. Semi-matchings for bipartite graphs and load balancing. Journal of Algorithms, 59(1):53–78, 2006.
• 11. Alexander V. Karzanov and S. Thomas McCormick. Polynomial methods for separable convex optimization in unimodular linear spaces with applications. SIAM Journal on Computing, 26(4):1245–1275, 1997.
• 12. Svetlana Kravchenko and Frank Werner. Minimizing the number of machines for scheduling jobs with equal processing times. European Journal of Operational Research, 199:595–600, 12 2009.
• 13. Svetlana Kravchenko and Frank Werner. Parallel machine problems with equal processing times: a survey. Journal of Scheduling, 14:435–444, 10 2011.
• 14. R. R. Meyer. A class of nonlinear integer programs solvable by a single linear program. SIAM J. Control Optim., 15(6):935–946, 1977.

Uwagi

1. Thematic Tracks Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).