Approximation algorithms for scheduling C-benevolent jobs on weighted machines

References

• Bar-Noy, A., Guha, S., Naor, J. and Schieber, B. (2001) Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing, 31(2), 331–352.
   Web of Science ®Google Scholar
• Baruah, S., Koren, G., Mao, D., Mishra, B., Raghunathan, A., Rosier, L., Shasha, D. and Wang, F. (1992) On the competitiveness of on-line real-time task scheduling. Real-Time Systems, 4(2), 125–144.
   Web of Science ®Google Scholar
• Brucker, P., Drexl, A., Möhring, R., Neumann, K. and Pesch, E. (1999) Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1), 3–41.
   Web of Science ®Google Scholar
• DasGupta, B. and Palis, M.A. (2001) Online real-time preemptive scheduling of jobs with deadlines on multiple machines. Journal of Scheduling, 4(6), 297–312.
   Web of Science ®Google Scholar
• Department of Homeland Security. (2016) Security screening. https://www.tsa.gov/travel/security-screening, accessed 05 July 2016.
   Google Scholar
• Epstein, L., Jez, L., Sgall, J. and van Stee, R. (2012) Online interval scheduling on uniformly related machines. Available at https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=online+interval+scheduling+for+uniformly+related+machines+2012&btnG=
   Google Scholar
• Epstein, L., Jeż, L., Sgall, J. and van Stee, R. (2016) Online scheduling of jobs with fixed start times on related machines. Algorithmica, 74(1), 156–176.
   Web of Science ®Google Scholar
• Epstein, L. and Levin, A. (2010) Improved randomized results for the interval selection problem. Theoretical Computer Science, 411(34-36), 3129–3135.
   Web of Science ®Google Scholar
• Erlebach, T. and Spieksma, F.C.R. (2003) Interval selection: Applications, algorithms, and lower bounds. Journal of Algorithms, 46(1), 27–53.
   Web of Science ®Google Scholar
• Faigle, U., Kern, W. and Nawijn, W.M. (1999) A greedy on-line algorithm for the k-track assignment problem. Journal of Algorithms, 31(1), 196–210.
   Web of Science ®Google Scholar
• Fung, S.P.Y., Poon, C.K. and Yung, K.W. (2012) On-line scheduling of equal-length intervals on parallel machines. Information Processing Letters, 112(10), 376–379.
   Web of Science ®Google Scholar
• Fung, S.P.Y., Poon, C.K. and Zheng, F. (2008) Online interval scheduling: Randomized and multiprocessor cases. Journal of Combinatorial Optimization, 16(3), 248–262.
   Web of Science ®Google Scholar
• Fung, S.P.Y., Poon, C.K. and Zheng, F. (2014) Improved randomized online scheduling of intervals and jobs. Theory of Computing Systems, 55(1), 202–228.
   Web of Science ®Google Scholar
• Krumke, S., Clemens Thielen, C. and Westphal, S. (2011) Interval scheduling on related machines. Computers & Operations Research, 38(12), 1836–1844.
   Web of Science ®Google Scholar
• Leonardi, S., Marchetti-Spaccamela, A. and Vitaletti, A. (2000) Approximation algorithms for bandwidth and storage allocation problems under real time constraints, in Proceedings of the International Conference on Foundations of Software Technology and Theoretical Computer Science, Springer, Berlin, Heidelberg, pp. 409–420.
   Google Scholar
• McLay, L.A., Jacobson, S.H. and Nikolaev, A.G. (2009) A sequential stochastic passenger screening problem for aviation security. IIE Transactions, 41(6), 575–591.
   Web of Science ®Google Scholar
• McLay, L.A., Lee, A. and Jacobson, S.H. (2010) Risk-based policies for airport security checkpoint screening. Transportation Science, 44(3), 333–349.
   Web of Science ®Google Scholar
• Miyazawa, H. and Erlebach, T. (2004) An improved randomized on-line algorithm for a weighted interval selection problem. Journal of Scheduling, 7(4), 293–311.
   Web of Science ®Google Scholar
• Ramos-Thuel, S. and Lehoczky, J.P. (1993) On-line scheduling of hard deadline aperiodic tasks in fixed-priority systems, in Proceedings of the Real-Time Systems Symposium, IEEE Press, Piscataway, NJ, pp. 160–171.
   Google Scholar
• Steiger, C., Walder, H. and Platzner, M. (2004) Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks. IEEE Transactions on Computers, 53(11), 1393–1407.
   Web of Science ®Google Scholar
• Woeginger, G.J. (1994) On-line scheduling of jobs with fixed start and end times. Theoretical Computer Science, 130(1), 5–16.
   Web of Science ®Google Scholar
• Yu, G. and Jacobson, S.H. (2018) Online C-benevolent job scheduling on multiple machines. Optimization Letters, 12(2), 251–263.
   Web of Science ®Google Scholar