×

zbMATH — the first resource for mathematics

NP-complete scheduling problems. (English) Zbl 0313.68054

MSC:
68Q45 Formal languages and automata
03D10 Turing machines and related notions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Graham, R.L., Bounds on multiprocessing anomalies and packing algorithms, (), 205-218
[2] Cook, S.A., The complexity of theorem proving procedures, (), 151-158 · Zbl 0363.68125
[3] Karp, R.M., Reducibility among combinatorial problems, () · Zbl 0366.68041
[4] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., ()
[5] Sethi, R., Complete register allocation problems, () · Zbl 0308.68018
[6] Bruno, J.; Coffman, E.G.; Sethi, R.; Bruno, J.; Coffman, E.G.; Sethi, R., Scheduling independent tasks to reduce Mean finishing time, Operating systems rev., Cacm, 17, 382-387, (1974), also see · Zbl 0283.68039
[7] Garey, M.R.; Johnson, D.S., Complexity results for multiprocessor scheduling under resource constraints, () · Zbl 0365.90076
[8] Coffman, E.G.; Graham, R.L., Optimal scheduling for two-processor systems, Acta. inf., 1, 200-213, (1972) · Zbl 0248.68023
[9] Fuji, M.; Kasami, T.; Ninomiya, N., Optimal sequence of two equivalent processors, SIAM J. appl. math., 17, 784-789, (1969) · Zbl 0205.48603
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.