Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems

References

• Adler M., Rosenberg A. L., Sitaraman R. K., Unger W. Scheduling time-constrained communication in linear networks. Proc. 10th Annual ACM Sympos. Parallel Algorithms Architectures (1998) 269–278Crossref, Google Scholar
• Arkin E. M., Silverberg E. B. Scheduling jobs with fixed start and end times. Discrete Appl. Math. (1987) 18:1–8Crossref, Google Scholar
• Baptiste P. Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. J. Scheduling (1999) 2:245–252Crossref, Google Scholar
• Bar-Noy A., Guha S., Naor J., Schieber B. Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput. (2001) 31(2):331–352Crossref, Google Scholar
• Bar-Noy A., Bar-Yehuda R., Freund A., Naor J., Schieber B. A unified approach to approximating resource allocation and scheduling. J. ACM (JACM) (2001) 48(5):1069–1090Crossref, Google Scholar
• Baruah S., Koren G., Mao D., Mishra B., Raghunathan A., Rosier L., Shasha D., Wang F. On the competitiveness of on-line real-time task scheduling. Real-Time Systems (1992) 4:125–144Crossref, Google Scholar
• Berman P., DasGupta B. Improvements in throughput maximization for real-time scheduling. Proc. 32nd Annual ACM Sympos. Theory Comput. (2000) May 2000Google Scholar
• Calinescu G., Chakrabarti A., Karloff H. J., Rabani Y. Improved approximation algorithms for resource allocation. IPCO 2002, the 9th Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science (2002) 2337(Springer-Verlag, Berlin, Germany) 401–414Crossref, Google Scholar
• Carlier J. Probléme à une machine et algorithmes polynômiaux. Questio (1981) 5(4):219–228Google Scholar
• Crama Y., Flippo O. E., van de Klundert J. J., Spieksma F. C. R. The assembly of printed circuit boards: A case with multiple machines and multiple board types. Eur. J. Oper. Res. (1997) 98:457–472Crossref, Google Scholar
• Faigle U., Nawijn W. M. Note on scheduling intervals on-line. Discrete Appl. Math. (1995) 58:13–17Crossref, Google Scholar
• Fischetti M., Martello S., Toth P. The fixed job schedule problem with spread-time constraints. Oper. Res. (1987) 35:849–858Link, Google Scholar
• Garey M. R., Johnson D. S. Two-processor scheduling with start times and deadlines. SIAM J. Comput. (1977) 6:416–426Crossref, Google Scholar
• Golumbic M. C.Algorithmic Graph Theory and Perfect Graphs (1980) (Academic Press, New York) Crossref, Google Scholar
• Graves S. C., Rinnooy Kan A. H. G., Zipkin P. H.Logistics for Production and Inventory. Vol. 4, Handbooks of Operations Research (1993) (North-Holland, Amsterdam, The Netherlands) Google Scholar
• Hall N. G., Magazine M. J. Maximizing the value of a space mission. Eur. J. Oper. Res. (1994) 78:224–241Crossref, Google Scholar
• Jackson J. R. Scheduling a production line to minimize maximum tardiness. (1955) . Management Science Research Project Report, Research Report 43, University of California, Los Angeles, CAGoogle Scholar
• Koren G. D. Shasha. An optimal on-line scheduling algorithm for overloaded real-time systems. SIAM J. Comput. (1995) 24:318–339Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Sequencing and scheduling: Algorithms and complexity. Logistics for Production and Inventory, Vol. 4, Handbooks of Operations Research (1993) (North-Holland, Amsterdam, The Netherlands) Crossref, Google Scholar
• Lipton R. J., Tomkins A. Online interval scheduling. Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms (1994) 302–311Google Scholar
• Liu H., Zarki M. E. Adaptive source rate control for real-time wireless video transmission. Mobile Networks Appl. (1998) 3:49–60Crossref, Google Scholar
• Moore J. M. An n-job, one machine sequencing algorithm for minimizing the number of late jobs. Management Sci. (1968) 15:102–109Link, Google Scholar
• Rajugopal G. R., Hafez R. H. M. Adaptive rate controlled, robust video communication over packet wireless networks. Mobile Networks Appl. (1998) 3:33–47Crossref, Google Scholar
• Sahni S. Algorithms for scheduling independent tasks. J. ACM (1976) 23:116–127Crossref, Google Scholar
• Spieksma F. C. R. On the approximability of an interval scheduling problem. J. Scheduling (1999) 2:215–227Crossref, Google Scholar
• Yau D. K. Y., Lam S. S. Adaptive rate-controlled scheduling for multimedia applications. IEEE/ACM Trans. Networking (1997) 5(4):475–488Crossref, Google Scholar