×

zbMATH — the first resource for mathematics

Inverval scheduling: a survey. (English) Zbl 1143.90337
Summary: In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given maximal machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution.

MSC:
90B35 Deterministic scheduling theory in operations research
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] , , Network flows, Prentice Hall, New Jersey, 1993.
[2] Anthonisse, Eur J Oper Res 15 pp 293– (1984)
[3] Arkin, Discrete Appl Math 18 pp 1– (1987)
[4] Bar-Noy, J ACM 48 pp 1069– (2005)
[5] Bar-Noy, SIAM J Comput 28 pp 1806– (2005)
[6] Bar-Noy, SIAM J Comput 31 pp 331– (2001)
[7] Beasley, Comput Oper Res 25 pp 567– (1998)
[8] Berman, Journal of Combinatorial Optimization 4 pp 307– (2000)
[9] , , , ” Algorithmic aspects of bandwidth trading,”In: Proceedings of the 30th International Conference on Automata, Languages, and Programming, Eindhoven, The Netherlands, Lecture Notes Comput Sci, 2719, 2003, pp. 751–766. · Zbl 1039.68535
[10] Biró, Discrete Math 100 pp 267Р(1992)
[11] , On-Line computation and competitive analysis, Cambridge University Press, Cambridge, 1988.
[12] On interval scheduling problems: A contribution, Ph.D. Thesis, Case Western Reserve University, Cleveland, Ohio, 1994.
[13] Bouzina, J Global Optim 9 pp 379– (1996)
[14] Brehob, IEEE Trans Comput 53 pp 73– (2004)
[15] Brucker, Computing 54 pp 97– (1994)
[16] Canetti, SIAM J Comput 27 pp 993– (1998)
[17] Carlisle, Discrete Appl Math 59 pp 225– (1995)
[18] Carter, Oper Res 40 pp s28– (1992)
[19] Chen, J Comput Biol 12 pp 129– (2005)
[20] , , , ” Machine minimization for scheduling jobs with interval constraints”, In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 81–90.
[21] , ” New hardness results for congestion minimization and machine scheduling”, In: Proceedings of the 36th ACM Symposium on the Theory of Computing, Chicago, Illinois, 2004, pp. 28–34. · Zbl 1192.90254
[22] Chuzhoy, Math of OR 31 pp 730– (2006)
[23] , , , , ” Scheduling with release times and deadlines on a minimum number of machines”, In: Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science, Toulouse, France, 2004, pp. 217–230.
[24] Dantzig, Nav Res Logist Q 1 pp 217– (1954)
[25] Dekel, Oper Res 31 pp 24– (1983)
[26] Dondeti, Oper Res 40 pp s76– (1992)
[27] Dondeti, Eur J Oper Res 70 pp 316– (1993)
[28] Erlebach, J Algorithm 46 pp 27– (2003)
[29] Faigle, J Algorithm 31 pp 196– (1999)
[30] Faigle, Discrete Appl Math 58 pp 13– (1995)
[31] Faneyte, Nav Res Logist 49 pp 743– (2001)
[32] Fischetti, Oper Res 35 pp 849– (1987)
[33] Fischetti, Oper Res 37 pp 395– (1989)
[34] Fischetti, Oper Res 40 pp s96– (1992)
[35] , Flows in networks, Princeton University Press, Princeton, New Jersey, 1962.
[36] Gabrel, Eur J Oper Res 83 pp 320– (1995)
[37] , Computers and intractability, a guide to the theory of NP-completeness, W.H. Freeman and Company, New York, 1979.
[38] Garey, SIAM J Algebr Discrete Math 1 pp 216– (1980)
[39] Gertsbakh, Oper Res 26 pp 68– (1978)
[40] Algorithmic graph theory and perfect graphs, Academic Press, San Diego, California, 1980. · Zbl 0541.05054
[41] , (Editors), Logistics of production and inventory, Handbooks in Operations Research and Management Science, Volume 4, North-Holland, Amsterdam, 1993.
[42] Gupta, IEEE Trans Comput C-28 pp 807– (1979)
[43] Goldman, J Algorithm 34 pp 370– (2000)
[44] Hall, Oper Res 49 pp 134– (2001)
[45] , Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th Design Automation Workshop, 1971, pp. 155–169.
[46] (Editor), Approximation algorithms for NP-hard problems, PWS Publishing Company, Boston, 1997.
[47] , ” Cost constrained fixed job scheduling,” In: Proceedings of the eighth Italian Conference on Theoretical Computer Science, Bertinoro, Italy, Lecture Notes Computer Sci 2841 ( 2003), 111–124. · Zbl 1257.68045
[48] , Resource allocation problems: Algorithmic approaches, The MIT Press, Cambridge, 1988. · Zbl 0786.90067
[49] Jansen, Eur J Oper Res 73 pp 127– (1994)
[50] Jansen, J Algorithm 34 pp 54– (2000)
[51] Keil, Oper Res Lett 12 pp 293– (1992)
[52] Kolen, Eur J Oper Res 54 pp 23– (1991)
[53] Kolen, Eur J Oper Res 64 pp 138– (1993)
[54] Kolen, Eur J Oper Res 79 pp 471– (1994)
[55] , ” Combinatorics in operations research,” Handbook of Combinatorics, , (Editors), North-Holland, Amsterdam, 1995, pp. 1875–1910. · Zbl 0854.90118
[56] Kroon, Eur J Oper Res 82 pp 190– (1995)
[57] Kroon, Oper Res 45 pp 624– (1997)
[58] , , , ” The optimal cost chromatic partition problem for trees and interval graphs,” In: Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, Como, Italy, 1197, Lecture Notes Comput Sci, 1996, 279–292. · doi:10.1007/3-540-62559-3_23
[59] ” Approximating circular arc colouring and bandwidth allocation in all-optical ring networks,” Proceedings of the first APPROX Conference, Lecture Notes Comput Sci, Volume 1444, Springer, Heidelberg, 1998, pp. 147–158. · Zbl 0902.68145
[60] , ” Online interval scheduling”, Proceedings of the fifth annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, 1994, pp. 302–311. · Zbl 0873.68012
[61] Martello, Eur J Oper Res 24 pp 106– (1986)
[62] Mingozzi, Oper Res 47 pp 873– (1999)
[63] Miyazawa, J Scheduling 7 pp 293– (2004)
[64] Nakajima, J Algorithm 3 pp 344– (1982)
[65] Nakajima, SIAM J Comput 11 pp 512– (1982)
[66] Private communication to J.K. Lenstra, April 25, 1982.
[67] Seiden, Oper Res Lett 22 pp 171– (1998)
[68] ” On-line scheduling – a survey,” Online Algorithms: The state of the art, Lecture Notes Comput Sci, Volume 1442, (Editors), Springer, Heidelberg, 1998, pp. 196–231.
[69] Spieksma, J Scheduling 2 pp 215– (1999)
[70] Approximation algorithms, Springer, Heidelberg, 2002.
[71] Woeginger, Theor Comput Sci 130 pp 5– (1994)
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.