Scheduling jobs with fixed start and end times. (English) Zbl 0636.90042

We analyze a scheduling problem in which each job has a fixed start and end time and a value. We describe an algorithm which maximizes the value of jobs completed by k identical machines. The algorithm runs in time \(O(n^ 2 \log n)\), where n is the number of jobs. We also show that the problem is NP-complete under the following restriction. Associated with each job is a subset of the machines on which it can be processed. For a fixed number of machines k, an \(O(n^{k+1})\) time algorithm is presented.


90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Dijkstra, E.W., A note on two problems in connexion with graphs, Numer. math., 1, 269-271, (1959) · Zbl 0092.16002
[2] Edmonds, J.; Karp, R.M., Theoretical improvements in algorithmic efficiency for network flow problems, J. assoc. comput. Mach., 19, 2, 248-264, (April 1972)
[3] Frank, A., On chain and antichain families of a partially ordered set, J. combin. theory, (ser. B), 29, 176-184, (1980) · Zbl 0443.06003
[4] Fredman, M.L.; Tarjan, R.E., Fibonacci heaps and their uses in improved network optimization algorithms, () · Zbl 1412.68048
[5] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[6] Greene, C.; Kleitman, D.J., The structure of sperner \(k- families\), J. combin. theory (ser. A), 20, 41-68, (1976) · Zbl 0361.05016
[7] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[8] Khachiyan, L.G.; Khachiyan, L.G., A polynomial algorithm in linear programming, Dokl. akad. nauk USSR, Soviet math. dokl., 20, 5, 191-194, (1979) · Zbl 0414.90086
[9] A. Kolen, J.K. Lenstra, C. Papadimitriou and J. Orlin, Interval scheduling problems, Manuscript, Centre of Mathematics and Computer Science, C.W.I., Kruislaan 413, 1098 SJ Amsterdam.
[10] Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0358.68059
[11] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1982), Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[12] M. Yannakakis, The node deletion problem for hereditary properties, Report No. TR-240, Computer Science Laboratory, Princeton University, Princeton, NJ. · Zbl 0436.68029
[13] M. Yannakakis, Node- and edge-deletion NP-complete problems, Proc. 10th Ann. ACM Symp. On Theory of Computing (Assoc. Comput. Mach., New York) 253-264. · Zbl 1282.68131
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.