Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Scheduling
Published in: Journal of Scheduling 1/2018

08-05-2017

A survey on how the structure of precedence constraints may change the complexity class of scheduling problems

Authors: D. Prot, O. Bellenguez-Morineau

Published in: Journal of Scheduling | Issue 1/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This survey aims to demonstrate that the structure of precedence constraints plays a tremendous role on the complexity of scheduling problems. Indeed, many problems can be \(\mathcal {NP}\)-hard when considering general precedence constraints, while they become polynomially solvable for particular precedence constraints. Additionally, the existence of many very exciting challenges in this research area is underlined.
previous article Journal of Scheduling (2018)
next article Case mix classification and a benchmark set for surgery scheduling

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now
Appendix
Available only for authorised users
Literature
Aho, I., & Mäkinen, E. (2006). On a parallel machine scheduling problem with precedence constraints. Journal of Scheduling, 9(5), 493–495.CrossRef
Ambühl, C., & Mastrolilli, M. (2009). Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica, 53(4), 488–503.CrossRef
Ambühl, C., Mastrolilli, M., Mutsanas, N., & Svensson, O. (2011). On the approximability of single-machine scheduling with precedence constraints. Mathematics of Operations Research, 36(4), 653–669.CrossRef
Baptiste, P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling, 2, 245–252.CrossRef
Baptiste, P., Brucker, P., Knust, S., & Timkovsky, V. G. (2004a). Ten notes on equal-execution-time scheduling. 4OR, 2, 111–127.CrossRef
Baptiste, P., Chrobak, M., Dürr, C., Jawor, W., & Vakhania, N. (2004b). Preemptive scheduling of equal-length jobs to maximize weighted throughput. Operations Research Letters, 32(3), 258–264.CrossRef
Baptiste, P., & Timkovsky, V. G. (2001). On preemption redundancy in scheduling unit processing time jobs on two parallel machines. Operations Research Letters, 28(5), 205–212.CrossRef
Baptiste, P., & Timkovsky, V. G. (2004). Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. Mathematical Methods of Operations Research, 60(1), 145–153.CrossRef
Brightwell, G. R., & Scheinerman, E. R. (1992). Fractional dimension of partial orders. Order, 9(2), 139–158.CrossRef
Brucker, P. (2007). Scheduling algorithms. New York: Springer.
Brucker, P., Garey, M. R., & Johnson, D. S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. Mathematics of Operations Research, 2(3), 275–284.CrossRef
Brucker, P., Hurink, J., & Knust, S. (2002). A polynomial algorithm for p| pj= 1, rj, outtree–cj. Mathematical Methods of Operations Research, 56(3), 407–412.CrossRef
Brucker, P., Hurink, J., & Kubiak, W. (1999). Scheduling identical jobs with chain precedence constraints on two uniform machines. Mathematical Methods of Operations Research, 49(2), 211–219.
Chardon, M., & Moukrim, A. (2005). The Coffman–Graham algorithm optimally solves uet task systems with overinterval orders. SIAM Journal on Discrete Mathematics, 19(1), 109–121.CrossRef
Chen, B., Coffman, E., Dereniowski, D., & Kubiak, W. (2015). Normal-form preemption sequences for an open problem in scheduling theory. Journal of Scheduling. doi:10.​1007/​s10951-015-0446-9.
Coffman, E. G, Jr., Dereniowski, D., & Kubiak, W. (2012). An efficient algorithm for finding ideal schedules. Acta Informatica, 49(1), 1–14.CrossRef
Coffman, E. G, Jr., & Graham, R. L. (1972). Optimal scheduling for two-processor systems. Acta Informatica, 1(3), 200–213.CrossRef
Correa, J. R., & Schulz, A. S. (2005). Single-machine scheduling with precedence constraints. Mathematics of Operations Research, 30(4), 1005–1021.CrossRef
Courcelle, B. (1990). The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1), 12–75.CrossRef
Dessouky, M. I., Lageweg, B. J., Lenstra, J. K., & van de Velde, S. L. (1990). Scheduling identical jobs on uniform parallel machines. Statistica Neerlandica, 44(3), 115–123.CrossRef
Djellab, K. (1999). Scheduling preemptive jobs with precedence constraints on parallel machines. European Journal of Operational Research, 117(2), 355–367.CrossRef
Dolev, D., & Warmuth, M. K. (1984). Scheduling precedence graphs of bounded height. Journal of Algorithms, 5(1), 48–59.CrossRef
Dolev, D., & Warmuth, M. K. (1985). Profile scheduling of opposing forests and level orders. SIAM Journal on Algebraic Discrete Methods, 6(4), 665–687.CrossRef
Downey, R. G., & Fellows, M. R. (2012). Parameterized complexity. New York: Springer.
Fellows, M. R., & McCartin, C. (2003). On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2), 317–324.CrossRef
Ganian, R., Hliněnỳ, P., Kneis, J., Langer, A., Obdržálek, J., & Rossmanith, P. (2014). Digraph width measures in parameterized algorithmics. Discrete Applied Mathematics, 168, 88–107.CrossRef
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: WH Freeman.
Garey, M. R., Johnson, D. S., Tarjan, R. E., & Yannakakis, M. (1983). Scheduling opposing forests. SIAM Journal on Algebraic Discrete Methods, 4(1), 72–93.CrossRef
Gonzalez, T. F., & Johnson, D. B. (1980). A new algorithm for preemptive scheduling of trees. Journal of the ACM (JACM), 27(2), 287–312.CrossRef
Gordon, V. S., Potts, C. N., Strusevich, V. A., & Whitehead, J. D. (2008). Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation. Journal of Scheduling, 11(5), 357–370.CrossRef
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.CrossRef
Hu, T. C. (1961). Parallel sequencing and assembly line problems. Operations Research, 9(6), 841–848.CrossRef
Huo, Y., & Leung, J. Y.-T. (2005). Minimizing total completion time for uet tasks with release time and outtree precedence constraints. Mathematical Methods of Operations Research, 62(2), 275–279.CrossRef
Huo, Y., & Leung, J. Y.-T. (2006). Minimizing mean flow time for uet tasks. ACM Transactions on Algorithms (TALG), 2(2), 244–262.CrossRef
Jianzhong, D., Leung, J. Y. T., & Young, G. H. (1991). Scheduling chain-structured tasks to minimize makespan and mean flow time. Information and Computation, 92(2), 219–236.CrossRef
Kubiak, W. (1989). Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints. Zeitschrift für Operations Research, 33(6), 423–437.
Kubiak, W., Rebaine, D., & Potts, C. (2009). Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors. Discrete Optimization, 6, 79–91.CrossRef
Lawler, E. L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics, 2, 75–90.CrossRef
Lawler, E. L. (1982). Preemptive scheduling of precedence-constrained jobs on parallel machines. In M. A. H. Dempster, J. K. Lenstra, & A. H. G. Rinnooy Kan (Eds.), Deterministic and stochastic scheduling, volume 84 of NATO advanced study institutes series (pp. 101–123). Netherlands: Springer.CrossRef
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Sequencing and scheduling. Handbooks in Operations Research and Management Science, 4, 445–522.CrossRef
Lenstra, J. K., & Rinnooy Kan, A. H. G. (1978). Complexity of scheduling under precedence constraints. Operations Research, 26(1), 22–35.CrossRef
Lenstra, J. K., & Rinnooy Kan, A. H. G. (1980). Complexity results for scheduling chains on a single machine. European Journal of Operational Research, 4(4), 270–275.CrossRef
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.CrossRef
Leung, J. Y.-T., & Young, G. H. (1990). Minimizing total tardiness on a single machine with precedence constraints. ORSA Journal on Computing, 2(4), 346–352.CrossRef
Lushchakova, I. N. (2006). Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints. European Journal of Operational Research, 171(1), 107–122.CrossRef
Middendorf, M., & Timkovsky, V. G. (1999). Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems. Journal of Combinatorial Optimization, 3(4), 417–435.CrossRef
Möhring, R. H. (1989). Computationally tractable classes of ordered sets. In I. Rival (Ed.), Algorithms and order, volume 255 of NATO ASI series (pp. 105–193). Netherlands: Springer.
Monma, C. L. (1982). Linear-time algorithms for scheduling on parallel processors. Operations Research, 30(1), 116–124.CrossRef
Monma, C. L., & Sidney, J. B. (1979). Sequencing with series-parallel precedence constraints. Mathematics of Operations Research, 4(3), 215–224.CrossRef
Moukrim, A. (1999). Optimal scheduling on parallel machines for a new order class. Operations Research Letters, 24(1), 91–95.CrossRef
Moukrim, A., & Quilliot, A. (1997). A relation between multiprocessor scheduling and linear programming. Order, 14(3), 269–278.CrossRef
Moukrim, A., & Quilliot, A. (2005). Optimal preemptive scheduling on a fixed number of identical parallel machines. Operations Research Letters, 33(2), 143–150.CrossRef
Muntz, R. R., & Coffman, E. G, Jr. (1970). Preemptive scheduling of real-time tasks on multiprocessor systems. Journal of the ACM (JACM), 17(2), 324–338.CrossRef
Papadimitriou, C. H., & Yannakakis, M. (1979). Scheduling interval-ordered tasks. SIAM Journal on Computing, 8(3), 405–409.CrossRef
Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems. New York: Springer.CrossRef
Robertson, N., & Seymour, P. D. (1986). Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3), 309–322.CrossRef
Sauer, N. W., & Stone, M. G. (1989). Preemptive scheduling of interval orders is polynomial. Order, 5(4), 345–348.CrossRef
Sidney, J. B. (1975). Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Operations Research, 23(2), 283–298.CrossRef
Svensson, O. (2011). Hardness of precedence constrained scheduling on identical machines. SIAM Journal on Computing, 40(5), 1258–1274.CrossRef
Tian, Z., Ng, C. T., & Cheng, T. C. E. (2006). An \({O}(n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness. Journal of Scheduling, 9(4), 343–364.CrossRef
Timkovsky, V. G. (2003). Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity. European Journal of Operational Research, 149(2), 355–376.CrossRef
Ullman, J. D. (1976). Complexity of sequencing problems. In J. L. Bruno, E. G. Coffman Jr., R. L. Graham, W. H. Kohler, R. Sethi, K. Steiglitz, & J. D. Ullman (Eds.), Computer and job/shop scheduling theory. New York: Wiley.
Wang, J.-B., Ng, C. T., & Cheng, T. C. E. (2008). Single-machine scheduling with deteriorating jobs under a series–parallel graph constraint. Computers and Operations Research, 35(8), 2684–2693.CrossRef
Wang, J.-B., & Wang, J.-J. (2013). Single-machine scheduling with precedence constraints and position-dependent processing times. Applied Mathematical Modelling, 37(3), 649–658.CrossRef
Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge: Cambridge University Press.CrossRef
Metadata
Title
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
Authors
D. Prot
O. Bellenguez-Morineau
Publication date
08-05-2017
Publisher
Springer US
Published in
Journal of Scheduling / Issue 1/2018
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-017-0519-z

Other articles of this Issue 1/2018

Journal of Scheduling 1/2018 Go to the issue

OriginalPaper

Scheduling electric vehicles and locating charging stations on a path

BriefCommunication

The Current state of bounds on benchmark instances of the job-shop scheduling problem

Editorial

Journal of Scheduling (2018)

OriginalPaper

Energy-efficient scheduling and routing via randomized rounding

OriginalPaper

Scheduling shared continuous resources on many-cores

OriginalPaper

Task assignment with start time-dependent processing times for personnel at check-in counters

Premium Partner

    Image Credits