Search

We investigate a semi-online variant of load balancing with restricted assignment. In this problem, we are given n jobs, which need to be processed by m machines with the goal to minimize the maximum machine load. Since strong lower bounds rule out any competitive ratio of o(log⁡n), we may reassign jobs at a certain job-individual cost. We generalize a result by Gupta, Kumar, and Stein (SODA 2014) by giving a O(log⁡log⁡mn)-competitive algorithm with constant amortized reassignment cost.

First investigations regarding dosimetric properties of the hybrid, pixelated, photon-counting Dosepix detector in the direct beam of a pulsed photon field (RQR8) for the personal dose equivalent $H\mathrm{_p(10)}$ are presented. The influence quantities such as pulse duration and dose rate were varied, and their responses were compared to the legal limits provided in PTB-A 23.2. The variation of pulse duration at a nearly constant dose rate of about 3.7$\,$Sv/h shows a flat response around 1.0 from 3.6$\,$s down to 2$\,$ms. A response close to 1.0 is achieved for dose rates from 0.07$\,$Sv/h to 35$\,$Sv/h for both pixel sizes. Above this dose rate, the large pixels (220$\,\mu$m edge length) are below the lower limit. The small pixels (55$\,\mu$m edge length) stay within limits up to 704$\,$Sv/h. The count rate linearity is compared to previous results, confirming the saturating count rate for high dose rates., Comment: 6 pages, 4 figures. This work was accepted for publication in IEEE Transactions on Nuclear Science

We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least $$1+\varepsilon $$ 1 + ε times its processing time, for some $$\varepsilon >0$$ ε > 0 . We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio of $$\mathcal {O}(1/\varepsilon )$$ O ( 1 / ε ) is the best possible (deterministic) for this problem. For commitment models, we give the first non-trivial performance bounds. If the commitment decisions must be made before a job’s slack becomes less than a $$\delta $$ δ -fraction of its size, we prove a competitive ratio of $$\mathcal {O}(\varepsilon /((\varepsilon -\delta )\delta ^2))$$ O ( ε / ( ( ε - δ ) δ 2 ) ) , for $$0 0 < δ < ε . When a provider must commit upon starting a job, our bound is $$\mathcal {O}(1/\varepsilon ^2)$$ O ( 1 / ε 2 ) . Finally, we observe that for scheduling with commitment the restriction to the “unweighted” throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms.