Search

Minimizing the sum of completion times when scheduling jobs on m identical parallel machines is a fundamental scheduling problem. Unlike the well-understood deterministic variant, it is a major open problem how to handle stochastic processing times. We show for the prominent class of index policies that no such policy can achieve a distribution-independent approximation factor. This strong lower bound holds even for simple instances with deterministic and two-point distributed jobs. For such instances, we give an O ( m ) -approximative list scheduling policy.

First measurements characterizing dosimetric properties of a dosimetry system designed for the purpose of active personal dosimetry for photons with mean energies from 12.4 to 1250 keV according to Physikalisch-Technische Bundesanstalt (PTB) requirements are presented. The system consists of three Dosepix detectors, which is a hybrid, pixelated, photon-counting X-ray detector. The energy and angular dependence of the normalized response and the coefficients of variation of the personal dose equivalents $H_{\mathrm{p}}{(10)}$ and $H_{\mathrm{p}}{(0.07)}$ are determined on an International Organization for Standardization (ISO) water slab phantom in continuous reference photon radiation fields according to ISO 4037-1 and ISO 4037-3. The energy response is presented for the narrow spectra N-15 to N-300 and the radiation qualities S-Cs and S-Co for angles of incidence of 0°, 30°, and ±60°. The highest deviation of the response from the reference response is found at N-60, −60° with 1.179 ± 0.007 (standard deviation) for $H_{\mathrm{p}}{(10)}$ . The energy range of use for $H_{\mathrm{p}}{(10)}$ is expected to extend from 12.4 to 1250 keV. For the personal dose equivalent $H_{\mathrm{p}}{(0.07)}$ , the normalized response at ±60° is below the lower limit for N-15, N-20, and N-25. It results in an energy range of use from 24.6 to 1250 keV. The coefficient of variation increases with increasing photon energy and stays below 1% for all measurements.

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.