# zbMATH — the first resource for mathematics

Fixed interval scheduling: models, applications, computational complexity and algorithms. (English) Zbl 1107.90019
Summary: The defining characteristic of fixed interval scheduling problems is that each job has a finite number of fixed processing intervals. A job can be processed only in one of its intervals on one of the available machines, or is not processed at all. A decision has to be made about a subset of the jobs to be processed and their assignment to the processing intervals such that the intervals on the same machine do not intersect. These problems arise naturally in different real-life operations planning situations, including the assignment of transports to loading/unloading terminals, work planning for personnel, computer wiring, bandwidth allocation of communication channels, printed circuit board manufacturing, gene identification and examining computer memory structures. We present a general formulation of the interval scheduling problem, show its relations to cognate problems in graph theory, and survey existing models, results on computational complexity and solution algorithms.

##### MSC:
 90B35 Deterministic scheduling theory in operations research 05C15 Coloring of graphs and hypergraphs 05C85 Graph algorithms (graph-theoretic aspects) 90C90 Applications of mathematical programming
DIMACS
Full Text:
##### References:
 [1] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows—theory, algorithms, and applications, (1993), Prentice-hall Englewood Cliffs, NJ · Zbl 1201.90001 [2] Arkin, E.M.; Silverberg, E.L., Scheduling jobs with fixed start and finish times, Discrete applied mathematics, 18, 1-8, (1987) · Zbl 0636.90042 [3] Babel, L., A fast algorithm for the maximum weight clique problem, Computing, 52, 31-38, (1994) · Zbl 0791.68127 [4] Bach, E.; Boyar, J.; Epstein, L.; Favrholdt, L.M.; Jiang, T.; Larsen, K.S.; Lin, G.-H.; van Stee, R., Tight bounds on the competitive ratio on accomodating sequences for the seat reservation problem, Journal of scheduling, 6, 131-147, (2003) · Zbl 1154.90405 [5] Balakrishnan, N.; Kanet, J.J.; Sridharan, S.V., Early/tardy scheduling with sequence dependent setups on uniform parallel machines, Computers and operations research, 26, 127-141, (1999) · Zbl 0947.90043 [6] Balas, E.; Chvátal, V.; Nešetril, J., On the maximum weight clique problem, Mathematics of operations research, 12, 522-535, (1987) · Zbl 0624.05040 [7] Battiti, R.; Protasi, M., Reactive local search for the maximum clique problem, Algorithmica, 29, 610-637, (2001) · Zbl 0985.68016 [8] Bar-Noy, A.; Bar-Yehuda, R.; Freund, A.; Naor, J.S.; Schieber, B., Approximating the throughput of multiple machines in real-time scheduling, SIAM journal on computing, 31, 331-352, (2001) · Zbl 0994.68073 [9] Bar-Noy, A.; Guha, S.; Naor, J.S.; Schieber, B., A unified approach to approximating resource allocation and scheduling, Journal of the ACM, 48, 1069-1090, (2001) · Zbl 1323.68564 [10] Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A., On the power of randomization in on-line algorithms, Algorithmica, 11, 2-14, (1994) · Zbl 0784.68038 [11] Bhatia, R.; Chuzhoy, J.; Freund, A.; Naor, J., Algorithmic aspects of bandwidth trading, Lecture notes in computer science, 2719, 751-766, (2003) · Zbl 1039.68535 [12] Bomze, I.M., On standard quadratic optimization problem, Journal of global optimization, 13, 369-387, (1998) · Zbl 0916.90214 [13] Bomze, I.M.; Budinich, M.; Pardalos, P.M.; Pelillo, M., The maximum clique problem, (), 1-74 · Zbl 1253.90188 [14] Bomze, I.M., Global escape strategies for maximizing quadratic forms over a simplex, Journal of global optimization, 11, 325-338, (1997) · Zbl 0904.90125 [15] Bouzina, K.I.; Emmons, H., Interval scheduling on identical machines, Journal of global optimization, 9, 379-393, (1996) · Zbl 0866.90069 [16] Boyar, J.; Larsen, K.S., The seat reservation problem, Algorithmica, 25, 403-417, (1999) · Zbl 0937.68156 [17] Brehob, M.; Wagner, S.; Torng, E.; Enbody, R., Optimal replacement is NP-hard for nonstandard caches, IEEE transactions on computers, 53, 73-76, (2004) [18] Brucker, P.; Nordmann, L., The k-track assignment problem, Computing, 52, 97-122, (1994) · Zbl 0822.90080 [19] Canetti, R.; Irani, S., Bounding the power of preemption in randomized scheduling, SIAM journal on computing, 27, 993-1015, (1998) · Zbl 0907.68007 [20] Carlisle, M.C.; Lloyd, E.L., On the k-coloring of intervals, Discrete applied mathematics, 59, 225-235, (1995) · Zbl 0826.68092 [21] Carter, M.W.; Tovey, C.A., When is the classroom assignment problem hard?, Operations research, 40, 28-39, (1992) · Zbl 0745.90049 [22] Chen, B.; Hassin, R.; Tzur, M., Allocation of bandwidth and storage, IIE transactions, 34, 501-507, (2002) [23] Chen, Z.Z.; Jiang, T.; Lin, G.H.; Rizzi, R.; Wen, J.J.; Xu, D.; Xu, Y., More reliable protein NMR peak assignment via improved 2-interval scheduling, Lecture notes in computer science, 2832, 580-592, (2003) · Zbl 1266.68227 [24] Chen, Z.-Z.; Jiang, T.; Lin, G.; Wen, J.; Xu, D.; Xu, J.; Xu, Y., Approximation algorithms for NMR spectral peak assignment, Theoretical computer science, 299, 211-229, (2003) · Zbl 1051.68113 [25] Chmeiss, A.; Jégou, P., A generalization of chordal graphs and the maximum clique problem, Information processing letters, 62, 61-66, (1997) · Zbl 1336.05110 [26] Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Seymour, P.; Vušković, K., Recognizing berge graphs, Combinatorica, 25, 143-187, (2005) · Zbl 1089.05027 [27] Chudnovsky, M.; Robertson, N.; Seymour, P.D.; Thomas, R., The strong perfect graph theorem, Annals of mathematics, 164, 51-229, (2006) · Zbl 1112.05042 [28] Chudnovsky, M.; Robertson, N.; Seymour, P.D.; Thomas, R., Progress on perfect graphs, Mathematical programming series B, 97, 405-422, (2003) · Zbl 1028.05035 [29] Dantzig, G.L.; Fulkerson, D.R., Minimizing the number of tankers to meet a fixed schedule, Naval research logistics quarterly, 1, 217-222, (1954) [30] Dijkstra, M.C.; Kroon, L.G.; van Nunen, J.A.E.E.; Salomon, M., A DSS for capacity planning of aircraft maintenance personnel, International journal of production research, 23, 69-78, (1991) [31] Dondeti, V.R.; Emmons, H., Fixed job scheduling with two types of processors, Operations research, 40, S76-S85, (1992) · Zbl 0813.90061 [32] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM journal on computing, 5, 691-703, (1976) · Zbl 0358.90021 [33] Erlebach, T.; Spieksma, F.C.R., Simple algorithms for a weighted interval selection problem, Lecture notes in computer science, 1969, 228-240, (2001) · Zbl 1044.68753 [34] Erlebach, T.; Spieksma, F.C.R., Interval selection: applications, algorithms, and lower bounds, Journal of algorithms, 46, 27-53, (2003) · Zbl 1033.90104 [35] Faigle, U.; Kern, W.; Nawijn, W.M., A greedy on-line algorithm for the k-track assignment problem, Journal of algorithms, 31, 196-210, (1999) · Zbl 0928.68125 [36] Faigle, U.; Nawijn, W.M., Note on scheduling intervals on-line, Discrete applied mathematics, 58, 13-17, (1995) · Zbl 0822.90082 [37] Faneyte, D.B.C.; Spieksma, F.C.R.; Woeginger, G.J., A branch-and-price algorithm for a hierarchical crew scheduling problem, Naval research logistics, 49, 743-759, (2002) · Zbl 1037.90029 [38] Fenet, S.; Solnon, C., Searching for maximum cliques with ant colony optimization, Lecture notes in computer science, 2611, 236-245, (2003) · Zbl 1033.68623 [39] Fischetti, M.; Martello, S.; Toth, P., Approximation algorithms for fixed job schedule problems, Operations research, 40, S96-S108, (1992) · Zbl 0764.90044 [40] Frank, A., On chain and antichain families of a partially ordered set, Journal of combinatorial theory series B, 29, 176-184, (1980) · Zbl 0443.06003 [41] Fujisawa, K.; Kojima, M.; Nakata, K., Exploiting sparsity in primal-dual interior-point methods for semidefinite programming, Mathematical programming, 79, 235-253, (1997) · Zbl 0887.90156 [42] Gabrel, V., Scheduling jobs within time windows on identical parallel machines: new model and algorithms, European journal of operational research, 83, 320-329, (1995) · Zbl 0904.90086 [43] Garey, M.R.; Johnson, D.S.; Miller, G.L., Papadimitriou, the complexity of coloring circular arcs and hords, SIAM journal on algebraic discrete methods, 1, 216-227, (1980) · Zbl 0499.05058 [44] Gavril, F., Maximum weight independent sets and cliques in intersection graphs of filaments, Information processing letters, 73, 181-188, (2000) · Zbl 1339.05287 [45] Gertsbakh, I.; Stern, H.I., Minimal resources for fixed and variable job schedules, Operations research, 18, 68-95, (1978) · Zbl 0371.90058 [46] Gibbons, L.E.; Hearn, D.W.; Pardalos, P.M.; Ramana, M.V., Continuous characterizations of the maximum clique problem, Mathematics of operations research, 22, 754-768, (1997) · Zbl 0883.90098 [47] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054 [48] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1993), Springer Berlin · Zbl 0837.05001 [49] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, (1981) · Zbl 0492.90056 [50] Grötschel, M.; Lovász, L.; Schrijver, A., Corrigendum to our paper, the ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 4, 291-295, (1984) · Zbl 0555.90080 [51] Gupta, U.I.; Lee, D.T.; Leung, J.Y.-T., An optimal solution for the channel-assignment problem, IEEE transactions on computers, 28, 807-810, (1979) · Zbl 0422.68031 [52] Harms, J.J., A simple optimal algorithm for scheduling variable-sized requests, Information processing letters, 68, 291-293, (1998) · Zbl 1339.90137 [53] A. Hashimoto, J. Stevens, Wire routing by optimizing channel assignment with large apertures, in: Proceedings of the 8th Design Automation Conference, 1971, pp. 155-169. [54] Heady, R.B.; Zhu, Z., Minimizing the sum of job earliness and tardiness in a multi-machine system, International journal of production research, 36, 1619-1632, (1998) · Zbl 0940.90504 [55] Hiraishi, K.; Levner, E.; Vlach, M., Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs, Computers and operations research, 29, 841-848, (2002) · Zbl 0999.68029 [56] Hsiao, J.Y.; Tang, C.Y.; Chang, R.S., An efficient algorithm for finding a maximum weight 2-independent set on interval graphs, Information processing letters, 43, 229-235, (1992) · Zbl 0764.68073 [57] W.L. Hsu, K.H. Tsai, A linear time algorithm for the two-track assignment problem, in: Proceedings of 27th Allerton Conference on Communication, Control and Computing, 1989, pp. 291-300. [58] () [59] Keil, J.M., On the complexity of scheduling tasks with discrete starting times, Operations research letters, 12, 293-295, (1992) · Zbl 0759.90045 [60] Khachiyan, L.G., A polynomial algorithm in linear programming, Dokladi akademii nauk SSSR, 244, 1093-1096, (1979) · Zbl 0414.90086 [61] Kolen, A.J.W.; Kroon, L.G., On the computational complexity of (maximum) class scheduling, European journal of operational research, 54, 23-28, (1991) [62] A.J.W. Kolen, J.K. Lenstra, Combinatorics in operations research, in: R. Graham et al. (Eds.), Handbooks of Combinatorics, vol. II. 1995, pp. 1901-1904. · Zbl 0854.90118 [63] Korst, J.; Aarts, E.; Lenstra, J.K.; Wessels, J., Periodic assignment and graph colouring, Discrete applied mathematics, 51, 291-305, (1994) · Zbl 0807.05030 [64] Kroon, L.G.; Salomon, M.; van Wassenhove, L.N., Exact and approximation algorithms for the tactical fixed interval scheduling problem, Operations research, 45, 624-638, (1997) · Zbl 0887.90089 [65] Lann, A.; Mosheiov, G., A note on the maximum number of on-time jobs on parallel identical machines, Computers and operations research, 30, 1745-1749, (2003) · Zbl 1039.90016 [66] Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart, and Winston New York · Zbl 0358.68059 [67] Lee, D.T.; Sarrafzadeh, M., Maximum independent set of a permutation graph in K-tracks, Lecture notes in computer science, 557, 2-11, (1991) [68] Lipton, R.J.; Tomkins, A., Online interval scheduling, (), 302-311 · Zbl 0873.68012 [69] Locatelli, M.; Bomze, I.M.; Pelillo, M., The combinatorics of pivoting for the maximum weight clique, Operations research letters, 32, 523-529, (2004) · Zbl 1054.90081 [70] D. Long, M. Thakur, Scheduling real-time disk transfers for continuous media applications, in: 12th IEEE Symposium on Mass Storage Systems, 1993, pp. 227-232. [71] Marchiori, E., Genetic, iterated and multistart local search for the maximum clique problem, Lecture notes in computer science, 2279, 112-121, (2002) · Zbl 1044.68780 [72] Martello, S.; Toth, P., A heuristic approach to the bus driver scheduling problem, European journal of operational research, 24, 106-117, (1986) · Zbl 0582.90073 [73] Miyazawa, H.; Erlebach, T., An improved randomized on-line algorithm for a weighted interval selection problem, Journal of scheduling, 7, 293-311, (2004) · Zbl 1154.90475 [74] Motzkin, T.S.; Straus, E.G., Maxima for graphs and a new proof of a theorem of Turán, Canadian journal of mathematics, 17, 533-540, (1965) · Zbl 0129.39902 [75] Naor, J.; Shachnai, H.; Tamir, T., Real-time scheduling with a budget, Lecture notes in computer science, 2719, 1123-1137, (2003) · Zbl 1039.68018 [76] Nemhauser, G.L.; Trotter, L.E., Properties of vertex packings and independence system polyhedra, Mathematical programming, 6, 48-61, (1974) · Zbl 0281.90072 [77] Nemhauser, G.L.; Trotter, L.E., Vertex packings: structural properties and algorithms, Mathematical programming, 8, 232-248, (1975) · Zbl 0314.90059 [78] C.T. Ng, M.Y. Kovalyov, T.C.E. Cheng, A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines, submitted for publication. [79] Pal, M.; Bhattacharjee, G.P., A sequential algorithm for finding a maximum weight K-independent set on interval graphs, International journal of computer mathematics, 60, 205-214, (1996) · Zbl 1001.68512 [80] Pardalos, P.M.; Rodgers, G.P., A branch and bound algorithm for the maximum clique problem, Computers and operations research, 19, 363-375, (1992) · Zbl 0757.90082 [81] Vavasis, S.A.; Ye, Y., A primal – dual interior point method whose running time depends only on the constraint matrix, Mathematical programming, 74, 79-120, (1996) · Zbl 0868.90081 [82] Saha, A.; Pal, M., Maximum weight k-independent set problem on permutation graphs, International journal of computer mathematics, 80, 1477-1487, (2003) · Zbl 1100.68597 [83] Sarrafzadeh, M.; Lou, R.D., Maximum k-covering of weighted transitive graphs with applications, Algorithmica, 9, 84-100, (1993) · Zbl 0766.68103 [84] Schrijver, A., Polyhedral proof methods in combinatorial optimization, Discrete applied mathematics, 14, 111-133, (1986) · Zbl 0602.90111 [85] Seiden, S.S., Randomized online interval scheduling, Operations research letters, 220, 171-177, (1998) · Zbl 0914.90168 [86] Sha, L.; Abdelzaher, T.; Arzen, K.-E.; Cervin, A.; Baker, T.; Burns, A.; Buttazzo, G.; Caccamo, M.; Lehoczky, J.; Mok, A.K., Real time scheduling theory: A historical perspective, Real-time systems, 28, 101-155, (2004) · Zbl 1073.68537 [87] Shor, N.Z., Convergence rate of the gradient descent method with dilatation of the space, Kibernetika, 2, 80-85, (1970) · Zbl 0243.90038 [88] N.Z. Shor, Dual quadratic estimates in polynomial and Boolean programming, in: P.M. Pardalos, J.B. Rosen (Eds.), Computational Methods of Global Optimization, Annals of Operations Research, vol. 25, 1990, pp. 163-168. · Zbl 0783.90081 [89] Sleator, D.; Tarjan, R., Amortized efficiency of List update and paging rules, Communications ACM, 28, 202-208, (1970) [90] Sivrikaya-Serifoglu, F.; Ulusoy, G., Parallel machine scheduling with earliness and tardiness penalties, Computers and operations research, 26, 773-787, (1999) · Zbl 0932.90016 [91] Spieksma, F.C.R., On the approximability of an interval scheduling problem, Journal of scheduling, 2, 215-227, (1999) · Zbl 0938.90034 [92] Torng, E., A unified analysis of paging and caching, Algorithmica, 20, 175-200, (1998) · Zbl 0895.68058 [93] Veeramachaneni, V.; Berman, P.; Miller, W., Aligning two fragmented sequences, Discrete applied mathematics, 127, 119-143, (2003) · Zbl 1014.92012 [94] Waterer, H.; Johnson, E.L.; Nobili, P.; Savelsbergh, M.W.P., The relation of time indexed formulations of single machine scheduling problems to the node packing problem, Mathematical programming series A, 93, 477-494, (2002) · Zbl 1023.90032 [95] Woeginger, G.J., On-line scheduling of jobs with fixed start and end times, Theoretical computer science, 130, 5-16, (1994) · Zbl 0810.68068 [96] Yannakakis, M.; Gavril, F., The maximum k-colorable subgraph problem for chordal graphs, Information processing letters, 24, 133-137, (1987) · Zbl 0653.68070
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.