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

Arkin, Esther M.; Silverberg, Ellen B.

Discrete Appl. Math. 18, 1-8 (1987).

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.

MSC:

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

Keywords:

clique; graph coloring; interval graphs; perfect graphs; shortest paths; fixed start and end time; identical machines; NP-complete

References:

[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