Abstract
A well studied and difficult class of scheduling problems con- cerns parallel machines and precedence constraints. In order to model more realistic situations, we consider precedence delays, associating with each precedence constraint a certain amount of time which must elapse between the completion and start times of the corresponding jobs. Re- lease dates, among others, may be modeled in this fashion. We provide the first constant-factor approximation algorithms for the makespan and the total weighted completion time objectives in this general class of problems. These algorithms are rather simple and practical forms of list scheduling. Our analysis also unifies and simplifies that of a number of special cases heretofore separately studied, while actually improving some of the former approximation results.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. von Arnim, R. Schrader, and Y. Wang. The permutahedron of N-sparse posets. Mathematical Programming, 75:1–18, 1996.
A. von Arnim and A. S. Schulz. Facets of the generalized permutahedron of a poset. Discrete Applied Mathematics, 72:179–192, 1997.
E. Balas, J. K. Lenstra, and A. Vazacopoulos. The one machine problem with delayed precedence constraints and its use in job-shop scheduling. Management Science, 41:94–109, 1995.
M. Bartusch, R. H. Möhring, and F. J. Radermacher. Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16:201–240, 1988.
D. Bernstein and I. Gertner. Scheduling expressions on a pipelined processor with a maximum delay of one cycle. ACM Transactions on Programming Languages and Systems, 11:57–66, 1989.
J. Bruno, J. W. Jones, and K. So. Deterministic scheduling with pipelined processors. IEEE Transactions on Computers, C-29:308–316, 1980.
S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein. Improved scheduling algorithms for minsum criteria. In F. Meyer auf der Heide and B. Monien, editors, Automata, Languages and Programming, LNCS, Vol. 1099, pages 646–657. Springer, Berlin, 1996.
C. S. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 609–618, 1997.
P. Chrétienne and C. Picouleau. Scheduling with communication delays: A survey. In P. Chrétienne, E. G. Coffman Jr., J. K. Lenstra, and Z. Liu, editors, Scheduling Theory and its Applications, chapter 4, pages 65–90. John Wiley & Sons, 1995.
F. A. Chudak and D. B. Shmoys. Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 581–590, 1997.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.
M. X. Goemans. Improved approximation algorithms for scheduling with release dates. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 591–598, 1997.
M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella, and Y. Wang. Single machine scheduling with release dates. Working paper, 1997.
R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Tech. J., 45:1563–1581, 1966.
R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5:287–326, 1979.
L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research, 22:513–544, 1997.
W. Herroelen and E. Demeulemeester. Recent advances in branch-and-bound procedures for resource-constrained project scheduling problems. In P. Chrétienne, E. G. Coffman Jr., J. K. Lenstra, and Z. Liu, editors, Scheduling Theory and its Applications, chapter 12, pages 259–276. John Wiley & Sons, 1995.
J. A. Hoogeveen, P. Schuurman, and G. J. Woeginger. Non-approximability results for scheduling problems with minsum criteria. In R. E. Bixby, E. A. Boyd, and R. Z. Ríos-Mercado, editors, Proceedings of the 6th International IPCO Conference, LNCS, Vol. 1412, pages 344–357. Springer, 1998. This volume.
J. A. Hoogeveen, B. Veltman, and J. K. Lenstra. Three, four, five, six, or the complexity of scheduling with communication delays. Operations Research Letters, 3:129–137, 1994.
J. M. Jaffe. Efficient scheduling of tasks without full use of processor resources. Theoretical Computer Science, 12:1–17, 1980.
E. Lawler, J. K. Lenstra, C. Martel, B. Simons, and L. Stockmeyer. Pipeline scheduling: A survey. Technical Report RJ 5738 (57717), IBM Research Division, San Jose, California, 1987.
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, Vol. 4, chapter 9, pages 445–522. North-Holland, Amsterdam, The Netherlands, 1993.
J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26:22–35, 1978.
J. Y.-T. Leung, O. Vornberger, and J. Witthoff. On some variants of the bandwidth minimization problem. SIAM J. Computing, 13:650–667, 1984.
R. H. Möhring, M. W. Schäffter, and A. S. Schulz. Scheduling jobs with communication delays: Using infeasible solutions for approximation. In J. Diaz and M. Serna, editors, Algorithms-ESA’96, LNCS, Vol. 1136, pages 76–90. Springer, Berlin, 1996.
A. Munier and J.-C. König. A heuristic for a scheduling problem with communication delays. Operations Research, 45:145–147, 1997.
A. Munier, M. Queyranne, and A. S. Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. Preprint 584/1998, Department of Mathematics, Technical University of Berlin, Berlin, Germany, 1998. ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/ Report-584-1998.ps.Z
K. W. Palem and B. Simons. Scheduling time critical instructions on RISC machines. In Proceedings of the 17th Annual Symposium on Principles of Programming Languages, pages 270–280, 1990.
C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. In Proceedings of the Fourth Workshop on Algorithms and Data Structures, LNCS, Vol. 955, pages 86–97. Springer, Berlin, 1995.
M. Queyranne. Structure of a simple scheduling polyhedron. Mathematical Programming, 58:263–285, 1993.
M. Queyranne and Y. Wang. Single-machine scheduling polyhedra with precedence constraints. Mathematics of Operations Research, 16:1–20, 1991.
V. J. Rayward-Smith. UET scheduling with unit interprocessor communication delays. Discrete Applied Mathematics, 18:55–71, 1987.
A. S. Schulz. Polytopes and Scheduling. PhD thesis, Technical University of Berlin, Berlin, Germany, 1996.
A. S. Schulz. Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. In W. H. Cunningham, S. T. McCormick, and M. Queyranne, editors, Integer Programming and Combinatorial Optimization, LNCS, Vol. 1084, pages 301–315. Springer, Berlin, 1996.
A. S. Schulz and M. Skutella. Random-based scheduling: New approximations and LP lower bounds. In J. Rolim, editor, Randomization and Approximation Techniques in Computer Science, LNCS, Vol. 1269, pages 119–133. Springer, Berlin, 1997.
A. S. Schulz and M. Skutella. Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. In R. Burkard and G. Woeginger, editors, Algorithms — ESA’97, LNCS, Vol. 1284, pages 416–429. Springer, Berlin, 1997.
E. D. Wikum, D. C. Llewellyn, and G. L. Nemhauser. One-machine generalized precedence constrained scheduling problems. Operations Research Letters, 16:87–89, 1994.
L. A. Wolsey, August 1985. Invited Talk at the 12th International Symposium on Mathematical Programming, MIT, Cambridge.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Munier, A., Queyranne, M., Schulz, A.S. (1998). Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds) Integer Programming and Combinatorial Optimization. IPCO 1998. Lecture Notes in Computer Science, vol 1412. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-69346-7_28
Download citation
DOI: https://doi.org/10.1007/3-540-69346-7_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64590-0
Online ISBN: 978-3-540-69346-8
eBook Packages: Springer Book Archive