Proceedings of the 18th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2023F4164

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 791–799 (2023)

Full text

Abstract. 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.

References

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.