Abstract
We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Blazewicz J., Lenstra J.K. and Rinnooy Kan A.H.G. (1983). Scheduling subject to resource constraints: Classification and complexity. Discr. Appl. Math. 5: 11–24
Chen Z.-L. (2004). Simultaneous job scheduling and resource allocation on parallel machines. Ann. Oper. Res. 129: 135–153
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding in bipartite graphs. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp.323–332. (2002).
Garey M.R. and Johnson D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completenes. Freeman, W.H. New York
Graham R.L. (1966). Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45: 1563–1581
Graham R.L. (1969). Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17: 416–429
Graham R.L., Lawler E.L., Lenstra J.K. and Rinnooy Kan A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discr. Math. 5: 287–326
Grigoriev, A., Kellerer, H., Strusevich, V.A.: Scheduling parallel dedicated machines with the speeding-up resource, manuscript (2003). Extended abstract. In: Proceedings of the 6th Workshop on Models and Algorithms for Planning and Scheduling Problems, pp. 131–132 (2003)
Grigoriev A., Sviridenko M., Uetz M.: Unrelated parallel machine scheduling with resource dependent processing times. In: Integer Programming and Combinatorial Optimization, Jünger, M., Kaibel, V. (eds.) Lecture Notes in Computer Science, 3509, pp. 182–195. Springer, Berlin Heidelberg New York (2005)
Grigoriev, A., Sviridenko, M., Uetz, M.: LP Rounding and an almost harmonic algorithm for scheduling with resource dependent processing times. In: Approximation, Randomization and Combinatorial Optimization, Diaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) Lecture Notes in Computer Science, 4110, pp. 140–151. Springer, Berlin Heidelberg New York (2006)
Grigoriev, A., Uetz, M.: Scheduling parallel jobs with linear speedup. In: Approximation and Online Algorithms. Erlebach, T., Persiano, P. (eds.) Lecture Notes in Computer Science, vol. 3879, pp. 203–215. Springer, Berlin Heidelberg New York (2006)
Hochbaum D.S. and Shmoys D.B. (1987). Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34: 144–162
Jansen K. (2004). Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme. Algorithmica 39: 59–81
Jansen K. and Mastrolilli M. (2004). Approximation schemes for parallel machine scheduling problems with controllable processing times. Comput. Oper. Res. 31: 1565–1581
Kellerer, H.: Personal Communication (2005)
Kellerer H. and Strusevich V.A. (2003). Scheduling parallel dedicated machines under a single non-shared resource. Euro. J. Oper. Res. 147: 345–364
Kellerer H. and Strusevich V.A. (2004). Scheduling problems for parallel dedicated machines under multiple resource constraints. Discr. Appl. Math. 133: 45–68
Kelley, J.E., Walker, M.R.: Critical Path Planning and Scheduling: An Introduction. Mauchly Associates, Ambler (PA) (1959)
Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: Approximation algorithms for scheduling on multiple machines. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 254–263 (2005)
Lenstra J.K., Shmoys D.B. and Tardos É. (1990). Approximation algorithms for scheduling unrelated parallel machines. Math. Progr. Ser. A 46: 259–271
Mounie, G., Rapine, C., Trystram, D.: Efficient approximation algorithms for scheduling malleable tasks. In: Proceedings of the 11th ACM Symposium on Parallel Algorithms and Architectures, pp. 23–32 (1999)
Mounie, G., Rapine, C., Trystram, D.: A 3/2-dual approximation algorithm for scheduling independent monotonic malleable tasks. Manuscript. Retrieved from http://citeseer.csail.mit.edu/558879.html
Shmoys D.B. and Tardos É. (1993). An approximation algorithm for the generalized assignment problem. Math. Progr. Ser. A 62: 461–474
Skutella M. (1998). Approximation algorithms for the discrete time-cost tradeoff problem. Math. Oper. Res. 23: 909–929
Turek, J., Wolf, J.L., Yu, P.S.: Approximate algorithms for scheduling parallelizable tasks. In: Proceedings of the 4th ACM symposium on parallel algorithms and architectures, pp. 323--332 (1992)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Grigoriev, A., Sviridenko, M. & Uetz, M. Machine scheduling with resource dependent processing times. Math. Program. 110, 209–228 (2007). https://doi.org/10.1007/s10107-006-0059-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0059-3